Meteor Shower

The first line contains two positive integers $n,r \text{ }(1 \le n \le 10^5, 1 \le r \le 10^9 )$ , representing the number of meteors and the radius of the earth.

For the following $n$ lines, each line contains four integers $x_i,y_i,dx_i, dy_i \text{ } (-10^9 \le x_i,y_i,dx_i,dy_i \le 10^9, (dx_i, dy_i) \neq (0,0))$ ; $(x_i,y_i)$ represents the start point of the $i$ -th meteor and $(dx_i,dy_i)$ represents the moving direction of the $i$ -th meteor.

It's guaranteed that the distance between origin $O$ and the start point of a meteor is at least $r+0.1$ .

Output $n$ lines, each line represents the answer of the $i$ -th meteor:

If the $i$ -th meteor collide with the Earth, output "Crash at $(x,y)$ "; $(x,y)$ is the point the meteorite crashed. If it does not, output "Observe at $(x,y)$ "; $(x,y)$ is the optimal observation point. (without quotes)

All the coordinates you output should be rounded into $4$ decimals, and the coordinates you output will be considered correct if the absolute error to the jury does not exceed $10^{-3}$ .

C++(g++ 7.5.0) 解法, 执行用时: 380ms, 内存消耗: 4536K, 提交时间: 2023-07-15 17:18:13

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const double eps = 1e-8;
double r;
void solve()
{
    double sx, sy, dx, dy;
    cin >> sx >> sy >> dx >> dy;
    double a = (dx * dx + dy * dy), b = (2 * sx * dx + 2 * sy * dy), c = (sx * sx + sy * sy - r * r);
    auto delta = b * b - 4ll * a * c;
    if (delta >= 0)
    {
        auto t1 = (-b + sqrt(delta)) / (2.0 * a), t2 = (-b - sqrt(delta)) / (2.0 * a);
        if (t2 < -eps)
        {
            dx = (sx);
            dy = (sy);
            auto tt = sqrt(1.0 * (r * r) / (dx * dx + dy * dy));
            printf("Observe at (%.4lf,%.4lf)\n", tt * dx, tt * dy);
        }
        else
            printf("Crash at (%.4lf,%.4lf)\n", sx + t2 * dx, sy + t2 * dy);
    }
    else
    {
        auto t =  -(sx * dx + sy * dy) / a;
        dx = (sx + max(t, 0.0) * dx);
        dy = (sy + max(t, 0.0) * dy);
        auto tt = sqrt(1.0 * (r * r) / (dx * dx + dy * dy));
        printf("Observe at (%.4lf,%.4lf)\n", tt * dx, tt * dy);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(4);
    int T;
    cin >> T >> r;
    while (T--)
        solve();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 738ms, 内存消耗: 4536K, 提交时间: 2023-07-01 22:04:09

#include <bits/stdc++.h>
#define pow2(a) ((a)*(a))
using namespace std;
typedef long long ll;
int n;
double r,x,y,dx,dy;
double ansx,ansy,a,h,l,b,c,h2;
int main() {
	cin>>n>>r;
	while(n--)
	{
		cin>>x>>y>>dx>>dy;
		a=1.0*abs(x*dx+y*dy)/sqrt(pow2(dx)+pow2(dy));
		h2=pow2(x)+pow2(y)-1.0*pow2(x*dx+y*dy)/(pow2(dx)+pow2(dy));
		h=sqrt(h2);
		c=sqrt(pow2(x)+pow2(y));
		
		if((pow2(dx)+pow2(dy))*(pow2(x)+pow2(y))-pow2(x*dx+y*dy)<=pow2(r)*(pow2(dx)+pow2(dy)))
		{
			if(-x*dx-y*dy<0)
			{
				ansx=1.0*x*r/c;
				ansy=1.0*y*r/c;
				printf("Observe at (%.4f,%.4f)\n",ansx,ansy);
			}
			else
			{
				b=sqrt(pow2(r)-pow2(h));
				l=a-b;
				ansx=x+1.0*l/sqrt(pow2(dx)+pow2(dy))*dx;
				ansy=y+1.0*l/sqrt(pow2(dx)+pow2(dy))*dy;
				printf("Crash at (%.4f,%.4f)\n",ansx,ansy);
			}
		}
		else
		{
			if(-x*dx-y*dy<0)
			{
				ansx=1.0*x/c*r;
				ansy=1.0*y/c*r;
			}
			else
			{
				ansx=(x+1.0*a/sqrt(pow2(dx)+pow2(dy))*dx)*r/h;
				ansy=(y+1.0*a/sqrt(pow2(dx)+pow2(dy))*dy)*r/h;
			}
			printf("Observe at (%.4f,%.4f)\n",ansx,ansy);
		}
	}

	return 0;
}

详情