星球大战

第一行包含一个正整数T(1<=T<=300)。
接下来有T组数据。
每组数据的第一行包含5个整数，x_a,y_a,x_r,r,n(1<=x_a,y_a,x_r,r<=15000；1<=n<=1000)，分别代表A的x坐标，A的y的坐标，反射装置的圆心的x坐标，反射装置的半径，与攻击次数。
我们保证攻击点A在圆外并且x_a>x_r;
接下来n行。每行包含2个整数 y₀,C_i(0<=y₀<=15000,0<=C_i<10⁹),代表A发出的攻击所想要攻击到的目标点（0，y₀）和这条激光的能量值C_i。

Python3(3.5.2) 解法, 执行用时: 716ms, 内存消耗: 4960K, 提交时间: 2018-12-22 18:58:08

while True:
    try:
        T=int(input())
        for i in range(T):
            fx,fy,rx,r,n=map(int,input().split())
            lens=(fx-rx)*(fx-rx)-r*r
            cnt=0
            all=0
            for j in range(n):
                y0,data=map(int,input().split())
                all+=data
                a=fy-y0
                b=-fx
                c=y0*fx
                d=(a*rx+b*fy+c)**2
                R=r*r*(a*a+b*b)
                if d<=R:
                    all=all-min(data,lens)
            print(all)
    except:
        break

C++14(g++5.4) 解法, 执行用时: 68ms, 内存消耗: 464K, 提交时间: 2019-11-21 20:57:46

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int t;cin>>t;
	while(t--){
		int xa,ya,xr,r,n;
		cin>>xa>>ya>>xr>>r>>n;
		ll E=(xa-xr)*(xa-xr)-r*r;
		ll T=r/sqrt((xa-xr)*(xa-xr)-r*r)*xa;
		ll sum=0;
		while(n--){
			ll y0,c;
			cin>>y0>>c;
			if(abs(y0-ya)<=T){
				ll cur=c-E;
				if(cur<0){
					cur=0;
				}
				sum+=cur;
			}else{
				sum+=c;
			}
		}
		cout<<sum<<endl;
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 82ms, 内存消耗: 504K, 提交时间: 2020-03-16 21:22:22

#include<iostream>
#include<cmath>
#define endl '\n'
using namespace std;
int t,xa,ya,xr,r,n,y,c;
#define ll long long
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>xa>>ya>>xr>>r>>n;
		ll ans=0;
		ll m=(xa-xr)*(xa-xr)-r*r;
		ll ym=xa/sqrt((xa-xr)*(xa-xr)-r*r)*r;
		while(n--)
		{
			cin>>y>>c;
			if(abs(y-ya)<=ym)
			{
				if(c>=m) ans+=c-m;
			}
			else
			ans+=c;
		}
		cout<<ans<<endl;
	}
}

详情