Shooting Practice
InterviewTime limit1sMemory limit1024 MB
Starting from the cursor at (0, 0), repeatedly shoot the farthest target and sum the squared distances from the cursor to each shot target over M moves.
- Level
Easy2 of 10
- Topics
- Simulation, Brute force
- Solved
- No attempts yet
Problem
Jeongwoo, who wants to improve his FPS game skills, is practicing target shooting. In this drill, the computer screen is treated as a two-dimensional coordinate plane, so the position of each target can be written as coordinates. Moving right increases the value, and moving up increases the value.
At the start, the mouse cursor is always at , and targets are on the screen. When the cursor moves to a target and clicks it, that target disappears and Jeongwoo earns points. The points earned equal the squared distance from the cursor's position before the move to that target. The distance is the Euclidean distance, which is the straight-line distance between two points.
Whenever a target is removed, a new target appears on the screen. Jeongwoo uses a strategy where each move hits the target that is farthest from the current cursor position. Find the total score Jeongwoo earns after repeating this process times. No two targets appear at the same position, and before each move the farthest target from the cursor is always unique.
Input
The first line contains two integers and , separated by a space.
From the second line onward, the next lines each contain two integers and , separated by a space, giving the coordinates of the targets currently on the screen.
The next lines each contain two integers and in order, giving the coordinates of the targets that appear next.
Output
Print the total score Jeongwoo earns.