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

View as PDF

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

Problem type

Given an axis-aligned rectangle with vertices at and and closed disks of radius 100, determine if there exists a path starting at and ending at where 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.

Input Specification

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

Each of the next lines contains a pair of integers and , indicating a center of one of the 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