Mock CCO '18 Contest 1 Problem 1 - A Geometry Problem

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type

Given an axis-aligned rectangle with vertices at (0, 0) and (L, W) and N closed disks of radius 100, determine if there exists a path starting at (0, y_s) and ending at (L, y_e) where 0 \le y_s, y_e \le W and where the path does not visit a point strictly outside the given rectangle or touching any of the disks.

In the event no such path exists, compute the minimum number of disks to remove such that a path can be constructed without exiting the rectangle or touching the remaining disks.

Constraints

1 \le W \le 50 \cdot 10^3

1 \le L \le 50 \cdot 10^3

1 \le N \le 250

0 \le X_i \le L

0 \le Y_i \le W

Input Specification

The first line will contain three space-separated integers, L, W, and N.

Each of the next N lines contains a pair of integers X_i and Y_i, indicating a center of one of the N disks.

Output Specification

Print, on a single line, the minimum number of disks to remove such that there exists a path connecting the left side of the rectangle to the right side of the rectangle that does not exit the rectangle or touch any of the disks.

Sample Input

130 340 5
10 50
130 130
70 170
0 180
60 260

Sample Output

1

Comments

There are no comments at the moment.