Colin heard that there will be a meteor shower in a few days. As a romantic boyfriend, he plans to take Eva to admire it.To simplify the problem, we will consider it on a two-dimensional plane.Assuming the Earth is a circle with origin OOO as its center and rrr as its radius. The points onthe circle form the surface of the Earth . A meteor shower contains nnn meteors. Each meteor is given by a point on the two-dimensional plane representing the point at which a meteor appears at a certain moment, and a direction vector representing the direction of its movement, the meteor will move continuously in this direction unless it collides with the Earth, that means we don't consider the collision between meteors .If it does, output "Crash at (x,y)(x,y)(x,y)", (x,y)(x,y)(x,y) is the point the meteorite crashed.All the coordinates you output should be rounded into 444 decimals.
Colin heard that there will be a meteor shower in a few days. As a romantic boyfriend, he plans to take Eva to admire it. To simplify the problem, we will consider it on a two-dimensional plane. Assuming the Earth is a circle with origin OOO as its center and rrr as its radius. The points on the circle form the surface of the Earth (i.e. points satisfy x2+y2=r2x^2+y^2=r^2x2+y2=r2). A meteor shower contains nnn meteors. Each meteor is given by a point (xi,yi)(x_i, y_i)(xi,yi) on the two-dimensional plane representing the point at which a meteor appears at a certain moment, and a direction vector (dxi,dyi)(dx_i, dy_i)(dxi,dyi) representing the direction of its movement, the meteor will move continuously in this direction unless it collides with the Earth, that means we don't consider the collision between meteors (i.e. the movements of different meteors are independent). In order to give Eva the best experience, Colin decided to take her to the optimal observation site, which is said to be the closest point on the surface of Earth to the trace of the given meteor. Watching a meteor is not always safe. Once a meteor collides with Earth, it is called a meteorite. If it will be a meteorite, Colin will take Eva to witness the place it crash. So Colin wants to know whether or not a meteor will collide with Earth (if it comes into contact with the Earth's surface, it is considered a collision). If it will, Colin wants to know the point it crash; and if not, Colin wants to know where the optimal observation site is. Please determine whether a meteor will collide with the Earth: If it does, output "Crash at (x,y)(x,y)(x,y)", (x,y)(x,y)(x,y) is the point the meteorite crashed. If it does not, output "Observe at (x,y)(x,y)(x,y)", (x,y)(x,y)(x,y) is the optimal observation point. All the coordinates you output should be rounded into 444 decimals.
![HBC252844[NOIP2018]赛道修建,启发式搜索(A*),贪心,搜索Meteor Shower题解
-第1张图片-东莞河马信息技术](https://www.xxstcz.com/zb_users/upload/2023/11/20231115215102170005626243025.jpeg "HBC252844[NOIP2018]赛道修建,启发式搜索(A*),贪心,搜索Meteor Shower题解
-第1张图片-东莞河马信息技术")
