Submission #985303

#	Time	Username	Problem	Language	Result	Execution time	Memory
985303		crimson231	Lonely mdic (kriii1_L)	C++17	0 / 1	14 ms	344 KiB

L

//#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-15;
//const ld PI = acos(-1);
//const int LEN = 25;
//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 sqr(ll x) { return x * x; }
//inline ld norm(ld th) {
//	while (th < 0) th += PI * 2;
//	while (th > PI * 2 - TOL) 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 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 = sqr((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 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
//	Arc(ld LO = 0, ld HI = 0) : lo(LO), hi(HI) {}
//	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 / 1;
//		//Pos HI = Pos(1, 0).rot(hi) * cen.r / 1;
//		//Pos vec = Pos(cen.c.x, cen.c.y);
//		//return (area() + vec / (HI + LO)) * .5;
//		int x = cen.c.x, y = cen.c.y, r = cen.r;
//		ld b = x * r * (sin(hi) - sin(lo));
//		ld d = 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;
//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() >= sqr(ra + rb)) return {};
//	if (vec.Euc() <= sqr(ra - rb)) return {};
//
//	//2nd hyprblc law of cos
//	ld X = (ra * ra - rb * rb + vec.Euc()) / (2 * distance * ra);
//	//if (X < -1 + TOL || X > 1 - TOL) return {};
//	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 ld union_except_x(const int& x, std::vector<Circle>& VC) {
//	ld union_area = 0;
//	int sz = VC.size();
//	std::vector<bool> V(sz, 0);
//	for (int i = 0; i < sz; i++) {
//		if (i == x || V[i]) continue;
//		Circle& disk = VC[i];
//		Arcs arcs = {};
//		for (int j = 0; j < sz; j++) {
//			if (j == x || j == i || V[j]) continue;
//			Pii vec = VC[i].c - VC[j].c;
//			int ra = VC[i].r, rb = VC[j].r;
//			if (vec.Euc() >= sqr(ra + rb)) continue;
//			if (vec.Euc() <= sqr(ra - rb) || VC[j] < VC[i] || VC[i] == VC[j]) { V[j] = 1; 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, PI * 2);
//				a2 = Arc(0, hi);
//				arcs.push_back(a1);
//				arcs.push_back(a2);
//			}
//			else {
//				a1 = Arc(lo, hi);
//				arcs.push_back(a1);
//			}
//		}
//
//		if (!arcs.size()) {
//			union_area += disk.A();
//			continue;
//		}
//
//		std::sort(arcs.begin(), arcs.end());
//		arcs.push_back(Arc(2 * PI, 2 * PI));
//		ld hi = 0;
//		for (const Arc& a : arcs) {
//			if (a.lo > hi) union_area += Arc(hi, a.lo).green(disk), 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;
//	//std::vector<Circle> tmp(N);
//	//std::vector<bool> VX(N, 0);
//	//for (Circle& c : tmp) std::cin >> c;
//	//for (int i = 0; i < N; i++) {//remove
//	//	if (VX[i]) continue;
//	//	for (int j = 0; j < N; j++) {
//	//		//if (i < j && tmp[i] == tmp[j]) V[i] = 1;
//	//		if (tmp[i] < tmp[j]) VX[i] = 1;
//	//		if (tmp[j] < tmp[i]) VX[j] = 1;
//	//	}
//	//}
//	//Disks VC;
//	//for (int i = 0; i < N; i++) {
//	//	if (!VX[i]) VC.push_back(tmp[i]);
//	//	if (VX[i]) ret++;
//	//}
//
//	int ret = 0;
//	std::cin >> N;
//	Disks VC(N);
//	for (Circle& c : VC) std::cin >> c;
//	std::sort(VC.begin(), VC.end(), cmpr);
//	int sz = VC.size();
//	ld U = union_except_x(-1, VC);
//	for (int x = 0; x < sz; x++) {
//		ld A = union_except_x(x, VC);
//		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
//
//
//
//*/


#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 = -1e17;
            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;
}

• Subtask 1: 0 / 1