-
Notifications
You must be signed in to change notification settings - Fork 0
/
oil2.cpp
91 lines (70 loc) · 1.95 KB
/
oil2.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
#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 Point reflection() const { return Point(-x, -y); }
inline Point operator-(const Point& p) const {
return Point(x - p.x, y - p.y);
}
inline ll operator^(const Point& p) const { return x * p.y - y * p.x; }
};
struct Segment {
Point p, q;
ll width() const { return abs(p.x - q.x); }
};
int N;
Segment segments[2001];
bool active[2001];
bool cmp(const tuple<Point, int, int>& a, const tuple<Point, int, int>& b) {
Point p = get<0>(a);
Point q = get<0>(b);
if (p.y < 0) p = p.reflection();
if (q.y < 0) q = q.reflection();
return (p ^ q) > 0;
}
ll maximum_amount(Point& center) {
vector<tuple<Point, int, int>> events;
for (int i = 0; i < N; i++) {
if (segments[i].p.y == center.y) continue;
events.push_back({segments[i].p - center, segments[i].width(), i});
events.push_back({segments[i].q - center, segments[i].width(), i});
}
sort(events.begin(), events.end(), cmp);
ll ans = 0;
ll curr = 0;
ll subtract = 0;
for (int i = 0; i < (int)events.size(); i++) {
auto [p, width, segment_idx] = events[i];
Point& next_point = get<0>(events[(i + 1) % events.size()]);
if (active[segment_idx])
subtract += width;
else {
curr += width;
ans = max(ans, curr);
}
active[segment_idx] = !active[segment_idx];
if ((p ^ next_point) == 0) continue;
curr -= subtract;
subtract = 0;
}
return ans;
}
int main() {
while (scanf("%d", &N) == 1) {
for (int i = 0; i < N; i++) {
ll x1, x2, y;
scanf("%lld %lld %lld", &x1, &x2, &y);
segments[i] = {Point(x1, y), Point(x2, y)};
}
ll ans = 0;
for (int i = 0; i < N; i++) {
Segment& s = segments[i];
ans = max(ans, s.width() + maximum_amount(s.p));
ans = max(ans, s.width() + maximum_amount(s.q));
}
printf("%lld\n", ans);
}
}