IOI 2003 Seeing the Boundary -

IOI 2003 Seeing the Boundary

[Memory: 32 MB CPU: 2 sec]

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 4N 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.

PROBLEM NAME: boundary

INPUT FORMAT:

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: Rock i’s description starts with a line containing a single integer pi (3 <= pi <= 20), the number of vertices in a rock’s base.

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.

OUTPUT FORMAT:

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

SAMPLE INPUT:

SAMPLE OUTPUT:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct P { int x, y; };
ll operator* (P p1, P p2) { return 1LL * p1.x * p2.y - 1LL * p1.y * p2.x; }
//mathmatical(right handed) coordinate system, x is east, y is north, z is toward people
//for positive cross product,  you get counter-clockwise angles as is the convention in mathematics.
P operator- (P p1, P p2) { P p = {p1.x-p2.x, p1.y-p2.y}; return p; }

// vector quadrants
// const int quads[2][2] = { {0,3} , {1,2} };
const int quads[2][2] = { {-1,-1} , {1,1} };
inline int get_quad(P &p){ return quads[p.x < 0][p.y < 0];}

struct Event {
    // is it the start?
    int start;
    // to pair with the end
    int id;
    // the actual location
    P loc;
};

bool operator < (Event a, Event b) {
    int aquad = get_quad(a.loc);
    int bquad = get_quad(b.loc);
    if (aquad == bquad) {
        long long cross = a.loc * b.loc;
        if (cross == 0) return a.start > b.start;
        return cross < 0;
    }
    return aquad < bquad;
}


int N, R;
P don;
vector<Event> events;

Event getnext(Event a) {
    int ax = a.loc.x + don.x, ay = a.loc.y + don.y;
    Event ans = {0, 0};
    if (ax == N) {
        if (ay) ans.loc = {N, ay - 1};
        else ans.loc = {N - 1, 0};
    }
    else if (ay == 0) {
        if (ax) ans.loc = {ax - 1, 0};
        else ans.loc = {0, 1};
    }
    else if (ax == 0) {
        if (ay < N) ans.loc = {0, ay + 1};
        else ans.loc = {1, N};
    }
    else {
        if (ax < N) ans.loc = {ax + 1, N};
        else ans.loc = {N, N - 1};
    }
    ans.loc.x -= don.x;
    ans.loc.y -= don.y;
    return ans;
}
int main() {
    cin >> N >> R;
    cin >> don.x >> don.y;
    for (int i = 0; i < R; i++) {
        int p; cin >> p;
        vector<P> rock(p);
        for (int j = 0; j < p; j++) {
            cin >> rock[j].x >> rock[j].y;
            rock[j].x -= don.x;
            rock[j].y -= don.y;
        }
        sort(rock.begin(), rock.end(), [](P a, P b) {return a * b < 0; });
        events.push_back({1, i, rock[0]});
        events.push_back({-1, i, rock[p - 1]});
    }

    sort(events.begin(), events.end());

    // pre-sweep
    int overlap = 0;
    vector<bool> activatedLine(R, false);

    for (auto curr : events) {
        if (curr.start == 1) {
            activatedLine[curr.id] = true;
        }
        else if (! activatedLine[curr.id]) {
            overlap++;
        }
    }

    // sweep sweep
    int ans = 0;
    int count = 0;
    Event post = {0, 0,  {0, N - don.y}};
    for (auto e : events) {
        while (count < 4 * N && post < e) {
            if (overlap == 0) {
                ans++;
            }
            post = getnext(post);
            count++;
        }
        if (e.start == 1) {
            overlap++;
        }
        else {
            overlap--;
        }
    }
    if (overlap == 0) {
        // add the rest if it's unblocked (no rocks there so not in loop)
        ans += 4 * N - count;
    }

    cout << ans;
}