The Winds of War
Time limit2sMemory limit512 MB
Choose a convex net containing the origin that covers as many enemy units as possible while covering as few friendly ones, and report the maximum difference.
- Level
Hard8 of 10
- Topics
- Geometry, Sorting, Dynamic programming, Brute force
- Solved
- No attempts yet
Problem
Colonel Trapp is trapped. After days of fighting General Position on a plateau, his mobile command unit is stuck at , on the edge of a cliff. But the winds are changing, and the Colonel has a secret weapon: the "epsilon net." As the Colonel's chief optimization officer, your job is to determine the maximum advantage the net can yield.
The epsilon net is a parachute-like device that you launch to cover any convex shape. (A shape is convex when, for every pair of points and it contains, it also contains the entire segment .) The net's shape must include the launch point .
The General has enemy units at fixed positions, and the Colonel has friendly units. The advantage of a chosen net shape equals the number of enemy units it covers minus the number of friendly units it covers. (The General is not a unit.)
You may assume that:
- no three of the points (Trapp's position , the enemy units, and the friendly units) lie on a single line;
- every two points have distinct -coordinates and distinct -coordinates;
- every unit has ;
- all coordinates are integers whose absolute value is at most ;
- the total number of units satisfies .
Input
The first line contains and , separated by a space. Each of the next lines contains the coordinates and of an enemy unit. Each of the following lines contains the coordinates of a friendly unit.
Output
Print a single line containing the maximum possible advantage.
Note

Figure 1: the sample input together with one optimal net.