Seeing the Boundary
Competition Day Two
August 20, 2003
Version 1.11
boundary
Seeing the Boundary

TASK

Farmer Don watches the fence that surrounds his N meter by N meter square, flat field (2
≤ N ≤ 500,000). One fence corner is at the origin (0, 0) and the opposite corner is at (N,
N); the sides of Farmer Don's fence are parallel to the X and Y axes.

Fence posts appear at all four corners and also at every meter along each side of the
fence, for a total of 4⋅N fence posts. The fence posts are vertical and are considered to
have no radius. Farmer Don wants to determine how many of his fence posts he can
watch when he stands at a given location within his fence.

Farmer Don’s field contains R (1 ≤ R ≤ 30,000) huge rocks that obscure his view of some
fence posts, as he is not tall enough to look over any of these rocks. The base of each
rock is a convex polygon with nonzero area whose vertices are at integer coordinates.
The rocks stand completely vertical. Rocks do not overlap, do not touch other rocks, and
do not touch Farmer Don or the fence. Farmer Don does not touch the fence, does not
stand within a rock, and does not stand on a rock.

Given the size of Farmer Don's fence, the locations and shapes of the rocks within it, and
the location where Farmer Don stands, compute the number of fence posts that Farmer
Don can see. If a vertex of a rock lines up perfectly with a fence post from Farmer Don's
location, he is not able to see that fence post.

Input: boundary.in

• The first line of input contains two space-separated integers: N and R.
• The next line of input contains two space-separated integers that specify the X
and Y coordinates of Farmer Don's location inside the fence.
• The rest of the input file describes the R rocks:
o Rock i’s description starts with a line containing a single integer pi (3 ≤ pi
≤ 20), the number of vertices in the rock's base.
o Each of the next pi lines contains a space-separated pair of integers that are
the X and Y coordinates of a vertex. The vertices of a rock’s base are
distinct and given in counterclockwise order.

Seeing the Boundary
Competition Day Two
August 20, 2003
Version 1.11
boundary

Example input

100 1
60 50
5
70 40
75 40
80 40
80 50
70 60
Note that the base of rock 1 has three
collinear vertices: (70,40), (75,40), and
(80,40)

Output: boundary.out

The output file should contain a single line with a single integer, the number of fence
posts visible to Farmer Don.

Example output:
319

Note (RiseOJ) — The original statement describes file-based input/output; on this judge your program must read from standard input and write to standard output instead.

Running time
1 second of CPU
Memory
64 MB

You will receive full points on each test case for which your program produces a correct
output file. No partial credit will be given on any test case.
X
Farmer Don
(0, 0)
(100, 100)
Y
Rock

생성자가 기록되지 않았습니다.

출처 IOI 2003