oj.uz

Submission #428498

# Submission time Handle Problem Language Result Execution time Memory
428498 2021-06-15T12:20:32 Z youngyojun 색종이 (kriii3_T) C++17
36 / 109
 116 ms 1392 KB 
#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 &th) {
	return cir.p.fi * cir.r * sin(th)
		+ cir.r * cir.r / 2 * (th + sin(th) * cos(th));
}
ld integral(const CIR &cir, const ld &s, const ld &e) {
	return integral(cir, e) - integral(cir, s);
}

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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1240 KB Output is correct
2 Correct 104 ms 1392 KB Output is correct
3 Correct 116 ms 1260 KB Output is correct
4 Correct 109 ms 1348 KB Output is correct
5 Correct 107 ms 1268 KB Output is correct
6 Correct 112 ms 1256 KB Output is correct
7 Correct 114 ms 1268 KB Output is correct
8 Correct 102 ms 1252 KB Output is correct
9 Correct 96 ms 1248 KB Output is correct
10 Correct 99 ms 1348 KB Output is correct
11 Correct 42 ms 1348 KB Output is correct
12 Correct 47 ms 1388 KB Output is correct
13 Correct 82 ms 1268 KB Output is correct
14 Correct 76 ms 1252 KB Output is correct
15 Correct 83 ms 1268 KB Output is correct
16 Correct 59 ms 1348 KB Output is correct

Subtask #2
0 / 73.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 1240 KB Output isn't correct
2 Halted 0 ms 0 KB -