## CCO '12 P6 - The Winds Of War

View as PDF

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 , 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 of points it contains, it also contains the entire line segment .) The net shape must include the launch point .

The General has enemy units stationed at fixed positions and the Colonel has 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 , enemy units, and friendly units) lie on a line,
• every two points have distinct -coordinates and -coordinates,
• all co-ordinates of the units have ,
• all co-ordinates are integers with absolute value at most , and
• the total number of units is between and .

#### Input Specification

The first line contains and then , separated by spaces. Subsequently there are lines of the form giving the enemy units' co-ordinates, and then 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

3
Figure 1: Sample input and an optimal net.