-
Notifications
You must be signed in to change notification settings - Fork 0
/
IOIBOUND-boundary_2003.cpp
105 lines (88 loc) · 3.01 KB
/
IOIBOUND-boundary_2003.cpp
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point(ll x, ll y) : x(x), y(y) {}
Point() {}
inline int quad() const { return y != 0 ? (y > 0) : x > 0; }
inline bool operator<(const Point& p) const {
return quad() != p.quad() ? quad() > p.quad() : (*this ^ p) > 0;
}
bool operator<=(const Point& p) const { return (*this < p) || zero_deg(p); }
inline Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
inline bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
inline void operator-=(const Point& p) { x -= p.x, y -= p.y; }
inline ll operator^(const Point& p) const { return x * p.y - y * p.x; }
inline ll operator*(const Point& p) const { return x * p.x + y * p.y; }
bool zero_deg(const Point& p) const {
return !(*this ^ p) && (*this * p) > 0;
}
};
struct Rock {
vector<Point> vertices;
Point endpoint_a, endpoint_b;
void compute_endpoints() {
endpoint_a = vertices.front();
endpoint_b = vertices.front();
for (Point& v : vertices) {
if ((endpoint_a ^ v) < 0) endpoint_a = v;
if ((endpoint_b ^ v) > 0) endpoint_b = v;
}
}
bool intersects_positive_x_axis() const { return endpoint_b < endpoint_a; }
};
int N, R, ev_n, curr_rocks_count;
Rock rocks[30001];
bool curr_rocks[30001];
pair<Point, int> events[2 * 30001];
Point origin, posts[4 * 500'201];
inline void toggle_rock(int rock_idx) {
curr_rocks[rock_idx] = !curr_rocks[rock_idx];
curr_rocks_count += curr_rocks[rock_idx] ? 1 : -1;
}
int radial_sweep() {
int visible = 0;
int p = 0;
for (int i = 0; i < ev_n; i++) {
int r_idx = events[i].second;
if (!curr_rocks[r_idx] && rocks[r_idx].intersects_positive_x_axis())
toggle_rock(r_idx);
}
for (int i = 0; i < ev_n; i++) {
auto [rock, r_idx] = events[i];
for (; posts[p] <= rock; p++)
visible += !curr_rocks_count && !rock.zero_deg(posts[p]);
toggle_rock(r_idx);
}
return curr_rocks_count ? visible : (visible + 4 * N - p);
}
void generate_posts(Point& origin) {
int i = 0;
posts[i++] = {N, origin.y};
while (posts[i - 1] != Point(N, N)) posts[i++] = {N, posts[i - 1].y + 1};
while (posts[i - 1] != Point{0, N}) posts[i++] = {posts[i - 1].x - 1, N};
while (posts[i - 1] != Point{0, 0}) posts[i++] = {0, posts[i - 1].y - 1};
while (posts[i - 1] != Point(N, 0)) posts[i++] = {posts[i - 1].x + 1, 0};
while (posts[i - 1] != Point{N, origin.y})
posts[i++] = {N, posts[i - 1].y + 1};
for (int p = 0; p < 4 * N; p++) posts[p] -= origin;
}
int main() {
scanf("%d %d %lld %lld", &N, &R, &origin.x, &origin.y);
generate_posts(origin);
for (int i = 0; i < R; i++) {
int p;
scanf("%d", &p);
while (p--) {
Point v;
scanf("%lld %lld", &v.x, &v.y);
rocks[i].vertices.push_back(v - origin);
}
rocks[i].compute_endpoints();
events[ev_n++] = make_pair(rocks[i].endpoint_a, i);
events[ev_n++] = make_pair(rocks[i].endpoint_b, i);
}
sort(events, events + ev_n);
printf("%d\n", radial_sweep());
}