DMOPC '15 Contest 2 P6 - Manhattan Magnets

Points: 17 (partial)

Time limit: 2.5s

Memory limit: 512M

Author:

Problem types

k_35P likes to play with magnets. He has placed $M$ $M$ magnets on the floor at integer coordinates, and will soon drop $N$ $N$ metal pieces. When dropped onto a floor, pieces of this metal will always land at integer coordinates, as if the floor was an infinitely large Cartesian plane.

Upon reaching the floor, a metal piece will also immediately move to the nearest (as per Manhattan distance) floor tile which has a magnet on it — the magnets do not move. If a metal piece is equidistant to two or more magnets that are tied for closest distance, it will not move, even if the magnets are at the same coordinates.

Before k_35P drops any metal, however, he's allowed you to place exactly one additional magnet at any integer coordinate on the floor (including directly under a tile where a piece of metal will land). You want to place this magnet such that it will collect as many pieces of metal as possible. Unable to solve this problem by hand, you've decided to write a program to determine the maximum number of metal pieces that your magnet can collect, if placed optimally.

Note

The Manhattan distance $d$ $d$ between a given point $P(x,y)$ $P (x, y)$ and another point $P'(x',y')$ $P^{'} (x^{'}, y^{'})$ is defined as $d = |x'-x|+|y'-y|$ $d = | x^{'} - x | + | y^{'} - y |$ .

Constraints

For 40% of the points, $N \le 50$ $N \leq 50$ .

For an additional 10% of the points, $N \le 5\,000$ $N \leq 5 000$ .

For all cases, $N \le 100\,000$ $N \leq 100 000$ .

Input Specification

The first line will contain $M$ $M$ $(1 \le M \le 10)$ $(1 \leq M \leq 10)$ .

In the next $M$ $M$ lines, line $i$ $i$ will contain two space-separated integers $x_i$ $x_{i}$ and $y_i$ $y_{i}$ $(0 \le x_i, y_i < 4\,000)$ $(0 \leq x_{i}, y_{i} < 4 000)$ , indicating the coordinates of the $i$ $i$ -th magnet.

The next line will contain a single integer $N$ $N$ $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ .

For the next $N$ $N$ lines, line $i$ $i$ will contain two space-separated integers $x_i$ $x_{i}$ and $y_i$ $y_{i}$ $(0 \le x_i, y_i < 4\,000)$ $(0 \leq x_{i}, y_{i} < 4 000)$ , indicating the coordinates where the $i$ $i$ -th piece of metal will be dropped.

Output Specification

A single integer, the maximum number of metal pieces you can collect by placing a single magnet.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

A magnet can be placed either directly where the first piece of metal will fall, or the second. Placing it anywhere else will result in it collecting no metal, as both pieces of metal are $1$ $1$ unit away from the magnet already set up.

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

Place a magnet at $(5,0)$ $(5, 0)$ , which will be $2$ $2$ units away from all metal pieces. Since each piece is $3$ $3$ units away from the nearest magnet, all $3$ $3$ can be collected by placing it here.

Sample Input 3

Copy

Sample Output 3

Copy

Comments

0

k_53P commented on Nov. 10, 2015, 11:52 p.m.

Sorry, the magnet must be placed at integer coordinates.

2

Riolku commented on March 16, 2021, 5:39 p.m.

The statement has been updated to use integer instead of integral, as it apparently confused some people.

0

JeffreyZ commented on Nov. 10, 2015, 10:41 p.m.

Can you place the new magnet on top of another magnet?

0

k_53P commented on Nov. 10, 2015, 10:45 p.m.

Yes.

0

JeffreyZ commented on Nov. 10, 2015, 10:50 p.m.

Sorry, should have specified: and a piece of metal that is closest to the two magnets on top of each other would not move?

0

FatalEagle commented on Nov. 10, 2015, 10:59 p.m.

This question can be answered unambiguously from the problem statement. Please reread it.

0

k_53P commented on Nov. 10, 2015, 10:57 p.m.

Do you mean a piece of metal which has the two magnets tied for the shortest distance?