-
Notifications
You must be signed in to change notification settings - Fork 0
/
BLMIRANA-mayonnaise_arrow.cpp
92 lines (70 loc) · 1.98 KB
/
BLMIRANA-mayonnaise_arrow.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
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
double cross(const Point& p) const { return x * p.y - y * p.x; }
double operator*(const Point& p) const { return x * p.x + y * p.y; }
double magnitude() const { return hypot(x, y); }
bool operator<(const Point& p) const {
return is_above() != p.is_above() ? is_above() : cross(p) > 0;
}
bool is_above() const { return y > 0 || (y == 0 && x > 0); }
bool acute(const Point& p) const { return (*this * p) > 0; }
bool deg0(const Point& p) const { return cross(p) == 0 && acute(p); }
};
struct Circle {
double x, y, radius;
bool touches_origin() const { return Point{x, y}.magnitude() <= radius; }
pair<Point, Point> points_of_tangency_from_origin() const {
const double a = radius;
const double b = hypot(x, y);
const double th = acos(a / b);
const double d = atan2(-y, -x);
const double d1 = d + th, d2 = d - th;
return {{x + a * cos(d1), y + a * sin(d1)}, {x + a * cos(d2), y + a * sin(d2)}};
}
};
void solve() {
int N;
cin >> N;
vector<Circle> circles(N);
for (Circle& c : circles) {
cin >> c.x >> c.y >> c.radius;
}
int curr = 0;
vector<pair<Point, bool>> events;
for (const Circle& c : circles) {
if (c.touches_origin()) {
curr++;
continue;
}
const auto [p1, p2] = c.points_of_tangency_from_origin();
if (p2 < p1) curr++;
events.emplace_back(p1, true);
events.emplace_back(p2, false);
}
sort(events.begin(), events.end());
int ans = 0;
int subtract = 0;
for (int i = 0; i < (int)events.size(); i++) {
const auto [p1, enter] = events[i];
const auto [p2, _] = events[(i + 1) % events.size()];
if (enter) {
curr++;
ans = max(ans, curr);
} else {
subtract++;
}
if (p1.deg0(p2)) continue;
curr -= subtract;
subtract = 0;
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while (T--) solve();
}