CCO '12 P6 - The Winds Of War

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2012 Stage 2, Day 2, Problem 3

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 \overline{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

  • no three points (Trapp's position (0, 0), enemy units, and friendly units) lie on a line,
  • every two points have distinct x-coordinates and y-coordinates,
  • all co-ordinates (x, y) of the units have y>0,
  • all co-ordinates are integers with absolute value at most 1\,000\,000\,000, and
  • the total number P+T of units is between 1 and 100.

Input Specification

The first line contains P and then T, separated by spaces. Subsequently there are P lines of the form x\ y giving the enemy units' co-ordinates, and then T lines giving the friendly units' co-ordinates.

Output Specification

Output a single line with the maximum possible advantage.

Sample Input

5 3
-8 4
-7 11
4 10
10 5
8 2
-5 7
-4 3
5 6

Output for Sample Input

Figure 1: Sample input and an optimal net.


There are no comments at the moment.