시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Colonel Trapp is trapped! For several days he has been fighting General Position on a plateau and his mobile command unit is now stuck at (0, 0), on the edge of a cliff. But the winds are changing! The Colonel has a secret weapon up his sleeve: the “epsilon net.” Your job, as the Colonel’s chief optimization officer, is to determine the maximum advantage that a net can yield.
The epsilon net is a device that looks like a parachute, which you can launch to cover any convex shape. (A shape is convex when, for every pair p, q of points it contains, it also contains the entire line segment pq.) The net shape must include the launch point (0, 0).
The General has P enemy units stationed at fixed positions and the Colonel has T friendly units. The advantage of a particular 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 can assume that
The first line contains P and then T, separated by spaces. Subsequently there are P lines of the form xy giving the enemy units’ co-ordinates, and then T lines giving the friendly units’ coordinates.
Output a single line with the maximum possible advantage.
5 3 -8 4 -7 11 4 10 10 5 8 2 -5 7 -4 3 5 6
3
Figure 1: Sample input and an optimal net