#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef double ld;
const ld PI = acos(-1);
const ld TOL = 1e-9;
struct Circle {
int x, y, r;
Circle(int X = 0, int Y = 0, int R = 0) : x(X), y(Y), r(R) {}
};
struct Event {
ld angle;
int type; // -1 for entering, 1 for exiting
int index;
Event(ld a, int t, int i) : angle(a), type(t), index(i) {}
bool operator<(const Event& e) const {
if (abs(angle - e.angle) > TOL)
return angle < e.angle;
return type > e.type; // start events (-1) come before end events (1)
}
};
bool circlesIntersect(const Circle& a, const Circle& b) {
ll dx = a.x - b.x;
ll dy = a.y - b.y;
ll distSq = dx * dx + dy * dy;
ll radSumSq = (ll)(a.r + b.r) * (a.r + b.r);
return distSq < radSumSq;
}
ld calculateUnionArea(const vector<Circle>& circles, int excludeIndex = -1) {
int n = circles.size();
vector<Event> events;
for (int i = 0; i < n; ++i) {
if (i == excludeIndex) continue;
Circle c = circles[i];
events.emplace_back(c.x - c.r, -1, i);
events.emplace_back(c.x + c.r, 1, i);
}
sort(events.begin(), events.end());
set<pair<int, int>> activeCircles;
ld unionArea = 0.0;
ld lastX = 0.0;
for (const auto& event : events) {
ld currentX = event.angle;
if (!activeCircles.empty()) {
ld width = currentX - lastX;
set<pair<int, int>> currentActiveCircles = activeCircles;
vector<pair<int, int>> segments;
for (const auto& circle : currentActiveCircles) {
int i = circle.second;
ld y1 = circles[i].y - sqrt((ld)circles[i].r * circles[i].r - (ld)(currentX - circles[i].x) * (currentX - circles[i].x));
ld y2 = circles[i].y + sqrt((ld)circles[i].r * circles[i].r - (ld)(currentX - circles[i].x) * (currentX - circles[i].x));
segments.emplace_back(y1, y2);
}
sort(segments.begin(), segments.end());
ld currentHeight = 0.0;
ld start = -INF;
for (const auto& seg : segments) {
if (seg.first > start) {
unionArea += currentHeight * width;
start = seg.first;
currentHeight = seg.second - seg.first;
} else {
if (seg.second > start) {
currentHeight += seg.second - start;
start = seg.second;
}
}
}
unionArea += currentHeight * width;
}
if (event.type == -1) {
activeCircles.insert({circles[event.index].y, event.index});
} else {
activeCircles.erase({circles[event.index].y, event.index});
}
lastX = currentX;
}
return unionArea;
}
void solve() {
int N;
cin >> N;
vector<Circle> circles(N);
for (int i = 0; i < N; ++i) {
cin >> circles[i].x >> circles[i].y >> circles[i].r;
}
ld totalUnionArea = calculateUnionArea(circles);
int count = 0;
for (int i = 0; i < N; ++i) {
ld unionAreaWithoutCircle = calculateUnionArea(circles, i);
if (abs(totalUnionArea - unionAreaWithoutCircle) < TOL) {
count++;
}
}
cout << count << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Compilation message
L.cpp: In function 'ld calculateUnionArea(const std::vector<Circle>&, int)':
L.cpp:77:25: error: 'INF' was not declared in this scope
77 | ld start = -INF;
| ^~~
