//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <deque>
typedef long long ll;
typedef double ld;
//typedef long double ld;
const ld INF = 1e17;
const ld TOL = 1e-10;
const ld PI = acos(-1);
const int LEN = 305;
int N, M, T, Q;
inline bool zero(const ld& x) { return std::abs(x) < TOL; }
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline ll sq(int x) { return (ll)x * x; }
inline ld norm(ld th) {
while (th < 0) th += PI * 2;
while (th > PI * 2 - TOL) th -= PI * 2;
//while (th >= PI * 2) th -= PI * 2;
return th;
}
//#define DEBUG
//#define ASSERT
struct Pii {
int x, y;
Pii(int X = 0, int Y = 0) : x(X), y(Y) {}
bool operator == (const Pii& p) const { return x == p.x && y == p.y; }
bool operator != (const Pii& p) const { return x != p.x || y != p.y; }
bool operator < (const Pii& p) const { return x == p.x ? y < p.y : x < p.x; }
bool operator <= (const Pii& p) const { return x == p.x ? y <= p.y : x <= p.x; }
Pii operator + (const Pii& p) const { return { x + p.x, y + p.y }; }
Pii operator - (const Pii& p) const { return { x - p.x, y - p.y }; }
Pii operator * (const int& n) const { return { x * n, y * n }; }
Pii operator / (const int& n) const { return { x / n, y / n }; }
ll operator * (const Pii& p) const { return { (ll)x * p.x + (ll)y * p.y }; }
ll operator / (const Pii& p) const { return { (ll)x * p.y - (ll)y * p.x }; }
Pii& operator += (const Pii& p) { x += p.x; y += p.y; return *this; }
Pii& operator -= (const Pii& p) { x -= p.x; y -= p.y; return *this; }
Pii& operator *= (const int& scale) { x *= scale; y *= scale; return *this; }
Pii& operator /= (const int& scale) { x /= scale; y /= scale; return *this; }
Pii operator ~ () const { return { -y, x }; }
Pii operator ! () const { return { -x, -y }; }
ll xy() const { return (ll)x * y; }
inline ll Euc() const { return (ll)x * x + (ll)y * y; }
inline ld rad() const { return norm(atan2(y, x)); }
int Man() const { return std::abs(x) + std::abs(y); }
ld mag() const { return hypot(x, y); }
inline friend std::istream& operator >> (std::istream& is, Pii& p) { is >> p.x >> p.y; return is; }
friend std::ostream& operator << (std::ostream& os, const Pii& p) { os << p.x << " " << p.y; return os; }
};
const Pii Oii = { 0, 0 };
const Pii INF_PT = { (int)INF, (int)INF };
inline ll cross(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) / (d3 - d2); }
inline ll cross(const Pii& d1, const Pii& d2, const Pii& d3, const Pii& d4) { return (d2 - d1) / (d4 - d3); }
inline ll dot(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) * (d3 - d2); }
inline ll dot(const Pii& d1, const Pii& d2, const Pii& d3, const Pii& d4) { return (d2 - d1) * (d4 - d3); }
inline int ccw(const Pii& d1, const Pii& d2, const Pii& d3) {
ll ret = cross(d1, d2, d3);
return !ret ? 0 : ret > 0 ? 1 : -1;
}
struct Pos {
ld x, y;
Pos(ld X = 0, ld Y = 0) : x(X), y(Y) {}
bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
bool operator != (const Pos& p) const { return !zero(x - p.x) || !zero(y - p.y); }
bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
ld operator * (const Pos& p) const { return x * p.x + y * p.y; }
ld operator / (const Pos& p) const { return x * p.y - y * p.x; }
Pos operator ^ (const Pos& p) const { return { x * p.x, y * p.y }; }
Pos operator - () const { return { -x, -y }; }
Pos operator ~ () const { return { -y, x }; }
Pos operator ! () const { return { y, x }; }
Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
Pos& operator *= (const ld& scale) { x *= scale; y *= scale; return *this; }
Pos& operator /= (const ld& scale) { x /= scale; y /= scale; return *this; }
ld xy() const { return x * y; }
inline Pos rot(ld the) const { return Pos(x * cos(the) - y * sin(the), x * sin(the) + y * cos(the)); }
inline ld Euc() const { return x * x + y * y; }
ld mag() const { return sqrt(Euc()); }
//ld mag() const { return hypotl(x, y); }
Pos unit() const { return *this / mag(); }
inline ld rad() const { return norm(atan2(y, x)); }
inline friend ld rad(const Pos& p1, const Pos& p2) { return norm(atan2(p1 / p2, p1 * p2)); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
bool close(const Pos& p) const { return zero((*this - p).Euc()); }
friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
};
const Pos O = Pos(0, 0);
typedef std::vector<Pos> Polygon;
inline ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
inline int ccw(const Pos& d1, const Pos& d2, const Pos& d3) {
ld ret = cross(d1, d2, d3);
return zero(ret) ? 0 : ret > 0 ? 1 : -1;
}
Pos intersection(const Pos& p1, const Pos& p2, const Pos& q1, const Pos& q2) {
ld a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
struct Circle {
Pii c;
int r;
Circle(Pii C = Pii(0, 0), int R = 0) : c(C), r(R) {}
bool operator == (const Circle& C) const { return c == C.c && r == C.r; }
bool operator != (const Circle& C) const { return !(*this == C); }
bool operator < (const Circle& q) const {
ll dist = sq((ll)r - q.r);
return r < q.r && dist >= (c - q.c).Euc();
}
bool operator > (const Pii& p) const { return r > (c - p).mag(); }
bool operator >= (const Pii& p) const { return r + TOL > (c - p).mag(); }
bool operator < (const Pii& p) const { return r < (c - p).mag(); }
Circle operator + (const Circle& C) const { return { c + C.c, r + C.r }; }
Circle operator - (const Circle& C) const { return { c - C.c, r - C.r }; }
ld H(const ld& th) const { return sin(th) * c.x + cos(th) * c.y + r; }//coord trans | check right
inline ld A() const { return 1. * r * r * PI; }
friend std::istream& operator >> (std::istream& is, Circle& c) { is >> c.c >> c.r; return is; }
friend std::ostream& operator << (std::ostream& os, const Circle& c) { os << c.c << " " << c.r; return os; }
};
inline bool cmpr(const Circle& p, const Circle& q) { return p.r > q.r; }//sort descending order
typedef std::vector<Circle> Disks;
struct Arc {
ld lo, hi;// [lo, hi] - radian range of arc, 0 ~ 2pi
int i;
Arc(ld LO = 0, ld HI = 0, int I = -1) : lo(LO), hi(HI), i(I) {}
bool operator < (const Arc& a) const { return zero(lo - a.lo) ? hi < a.hi : lo < a.lo; }
inline ld area(const Circle& cen) const { return (hi - lo) * cen.r * cen.r; }
inline ld green(const Circle& cen) const {
Pos LO = -Pos(1, 0).rot(lo) * cen.r;
Pos HI = Pos(1, 0).rot(hi) * cen.r;
Pos vec = Pos(cen.c.x, cen.c.y);
return (area(cen) + vec / (HI + LO)) * .5;
//int x = cen.c.x, y = cen.c.y, r = cen.r;
//ld b = 1. * x * r * (sin(hi) - sin(lo));
//ld d = 1. * y * r * (cos(lo) - cos(hi));
//return (area(cen) + b + d) * .5;
}
friend std::ostream& operator << (std::ostream& os, const Arc& l) { os << l.lo << " " << l.hi; return os; }
};
typedef std::vector<Arc> Arcs;
Arcs VA[LEN];
bool V[LEN];
bool P[LEN];
inline std::vector<Pos> intersection(const Circle& a, const Circle& b) {
Pii ca = a.c, cb = b.c;
Pii vec = cb - ca;
ll ra = a.r, rb = b.r;
ld distance = vec.mag();
ld rd = vec.rad();
if (vec.Euc() >= sq(ra + rb)) return {};
if (vec.Euc() <= sq(ra - rb)) return {};
//2nd hyprblc law of cos
ld X = (ra * ra - rb * rb + vec.Euc()) / (2 * distance * ra);
if (X < -1) X = -1;
if (X > 1) X = 1;
ld h = acos(X);
if (zero(h)) return {};
return { Pos(norm(rd - h), norm(rd + h)) };
}
inline void arc_init(std::vector<Circle>& VC) {
std::sort(VC.begin(), VC.end(), cmpr);
int sz = VC.size();
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
Pii vec = VC[i].c - VC[j].c;
int ra = VC[i].r, rb = VC[j].r;
if (vec.Euc() >= sq(ra + rb)) continue;
if (vec.Euc() <= sq(ra - rb)) continue;
auto inx = intersection(VC[i], VC[j]);
if (!inx.size()) continue;
ld lo = inx[0].x;
ld hi = inx[0].y;
Arc a1, a2;
if (lo > hi) {
a1 = Arc(lo, 2 * PI, j);
a2 = Arc(0, hi, j);
VA[i].push_back(a1);
VA[i].push_back(a2);
}
else {
a1 = Arc(lo, hi, j);
VA[i].push_back(a1);
}
}
std::sort(VA[i].begin(), VA[i].end());
VA[i].push_back(Arc(2 * PI, 2 * PI, -2));
}
return;
}
inline ld union_except_x(const std::vector<Circle>& VC, const int& x = -1) {
memset(V, 0, sizeof V);
int sz = VC.size();
for (int i = 0; i < sz; i++) {
if (i == x || V[i]) continue;
for (int j = 0; j < sz; j++) {
if (j == x || j == i || V[j]) continue;
if (VC[j] < VC[i] || VC[j] == VC[i]) { V[j] = 1; continue; }
}
}
ld union_area = 0;
for (int i = 0; i < sz; i++) {
if (i == x || V[i]) continue;
ld hi = 0;
for (const Arc& a : VA[i]) {
if (a.i == x || V[a.i]) continue;
if (a.lo > hi) union_area += Arc(hi, a.lo).green(VC[i]), hi = a.hi;
else hi = std::max(hi, a.hi);
}
}
return union_area;
}
inline void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
int ret = 0;
std::cin >> N;
Disks VC(N);
for (Circle& c : VC) std::cin >> c;
arc_init(VC);
int sz = VC.size();
ld U = union_except_x(VC);
for (int x = 0; x < sz; x++) {
if (V[x]) { ret++; continue; }
ld A = union_except_x(VC, x);
ret += zero(U - A);//no-dabwon
}
std::cout << ret << "\n";
}
int main() { solve(); return 0; }//boj10900 lonely mdic
/*
3
3 0 4
-3 0 4
0 0 2
5
0 0 1
1 1 1
-1 1 1
-1 -1 1
1 -1 1
9
3 0 4
-3 0 4
0 0 2
9 0 4
6 0 2
15 0 4
12 0 2
21 0 4
18 0 2
5
1000 1000 1415
1000 -1000 1415
-1000 -1000 1415
-1000 1000 1415
0 0 1
5
1000 1000 1414
1000 -1000 1414
-1000 -1000 1414
-1000 1000 1414
0 0 1
5
0 0 1
2 0 1
4 0 1
6 0 1
8 0 1
5
0 0 1
1 0 1
2 0 1
3 0 1
4 0 1
8
-1 2 1000
-2 1 1000
-2 -1 1000
-1 -2 1000
1 -2 1000
2 -1 1000
2 1 1000
1 2 1000
5
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Correct |
15 ms |
344 KB |
Output is correct |
| 4 |
Correct |
15 ms |
560 KB |
Output is correct |
| 5 |
Correct |
29 ms |
520 KB |
Output is correct |
| 6 |
Correct |
34 ms |
348 KB |
Output is correct |
| 7 |
Correct |
68 ms |
3052 KB |
Output is correct |
| 8 |
Correct |
22 ms |
3932 KB |
Output is correct |
| 9 |
Correct |
14 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
34 ms |
3676 KB |
Output is correct |
| 11 |
Correct |
63 ms |
1884 KB |
Output is correct |
| 12 |
Correct |
23 ms |
856 KB |
Output is correct |
| 13 |
Correct |
12 ms |
1628 KB |
Output is correct |
| 14 |
Correct |
47 ms |
596 KB |
Output is correct |
| 15 |
Correct |
26 ms |
344 KB |
Output is correct |
| 16 |
Correct |
12 ms |
2392 KB |
Output is correct |
