Submission #428513

#	Time	Username	Problem	Language	Result	Execution time	Memory
428513		youngyojun	색종이 (kriii3_T)	C++17	36 / 109	144 ms	1348 KiB

paper

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) (V).begin(),(V).end()
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef pair<ld, ld> pdd;
const ld PI = acos(0)*2;
const ld eps = 1e-12;
bool isZero(const ld &x) { return -eps <= x && x <= eps; }
bool isSame(const ld &a, const ld &b) { return isZero(a-b); }
ld norm(ld theta) {
	theta = fmod(theta, PI*2);
	while(theta < 0) theta += PI*2;
	return theta;
}
bool operator == (const pdd &a, const pdd &b) { return isSame(a.fi, b.fi) && isSame(a.se, b.se); }
bool operator != (const pdd &a, const pdd &b) { return !(a == b); }
pdd operator + (const pdd &a, const pdd &b) { return pdd(a.fi + b.fi, a.se + b.se); }
pdd operator - (const pdd &a, const pdd &b) { return pdd(a.fi - b.fi, a.se - b.se); }
pdd operator * (const pdd &a, const ld &b) { return pdd(a.fi * b, a.se * b); }
pdd operator / (const pdd &a, const ld &b) { return pdd(a.fi / b, a.se / b); }
ld operator * (const pdd &a, const pdd &b) { return a.fi * b.se - a.se * b.fi; }
ld operator / (const pdd &a, const pdd &b) { return a.fi * b.fi + a.se * b.se; }
ld dist2(const pdd &v) { return v/v; }
pdd rotNVec(const ld &theta) { return pdd(cos(theta), sin(theta)); }
ld ccw(const pdd &a, const pdd &b, const pdd &c) { return a*b + b*c + c*a; }

pdd readPdd() {
	pdd p;
	cin >> p.fi >> p.se;
	return p;
}

struct LINE {
	LINE(pdd s, pdd e)
		: s(s), e(e) {}
	pdd s, e;
};

struct TRI {
	pdd p[3];

	void input() {
		for(int i = 3; i--;)
			p[i] = readPdd();
		if(ccw(p[0], p[1], p[2]) <= 0)
			swap(p[1], p[2]);
	}
};

struct CIR {
	int idx;

	pdd p;
	ld r;

	void input() {
		p = readPdd();
		cin >> r;
	}
};

bool isSame(const CIR &a, const CIR &b) {
	return a.p == b.p && isSame(a.r, b.r);
}

bool isIn(const CIR &a, const pdd &p) {
	return dist2(p - a.p) <= a.r*a.r - eps;
}

ld integral(const CIR &cir, const ld &s, const ld &e) {
	return cir.p.fi * cir.r * (sin(e) - sin(s))
		+ cir.r * cir.r * (e-s + (sin(e+e) - sin(s+s)) / 2) / 2;
}

bool cirInsec(const pdd &p, const ld &r, const ld &R, ld &th1, ld &th2) {
	ld d2 = p/p, d = sqrt(d2);
	ld cosGamma = (r*r + d2 - R*R) / (r*d*2);
	if(cosGamma < -1 || 1 < cosGamma)
		return false;
	
	ld gamma = acos(cosGamma);
	ld phi = atan2(p.se, p.fi);

	th1 = norm(PI + phi - gamma);
	th2 = norm(PI + phi + gamma);
	if(th1 > th2) swap(th1, th2);
	return true;
}



vector<CIR> CV;

ld Ans[205][205];

int N;

void solveCir() {
	for(const CIR &cir : CV) {
		const int idx = cir.idx;

		vector<ld> V = {0, PI*2};

		for(const CIR &o : CV) if(!isSame(cir, o)) {
			ld th1, th2;
			if(cirInsec(cir.p - o.p, cir.r, o.r, th1, th2)) {
				V.eb(th1);
				V.eb(th2);
			}
		}

		sort(allv(V));
		V.erase(unique(allv(V), [&](const ld &a, const ld &b) {
			return isSame(a, b);
		}), V.end());

		int n = sz(V);
		for(int i = 1; i < n; i++) {
			ld ths = V[i-1], the = V[i];
			ld val = integral(cir, ths, the);
			pdd cp = cir.p + rotNVec((ths + the) / 2) * cir.r;

			int si = 0, ei = N+1;

			for(const CIR &o : CV) {
				if(si < o.idx && o.idx < idx) {
					if(!isSame(cir, o) && isIn(o, cp))
						si = o.idx;
				} else if(idx < o.idx && o.idx < ei) {
					if(isSame(cir, o) || isIn(o, cp))
						ei = o.idx;
				}
			}

			for(int i = idx; i < ei; i++) {
				Ans[i][idx] += val;
				Ans[i][si] -= val;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		int t; cin >> t;
		if(1 == t) {
			// TRI
		} else {
			CV.eb();
			CV.back().idx = i;
			CV.back().input();
		}
	}

	solveCir();

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= i; j++)
			printf("%.15Lf ", Ans[i][j]);
		putchar('\n');
	}
	return 0;
}

• Subtask 1: 36 / 36
• Subtask 2: 0 / 73