oj.uz

Submission #428513

# Submission time Handle Problem Language Result Execution time Memory
428513 2021-06-15T12:28:09 Z youngyojun 색종이 (kriii3_T) C++17
36 / 109
 144 ms 1348 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 &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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1348 KB Output is correct
2 Correct 119 ms 1348 KB Output is correct
3 Correct 125 ms 1348 KB Output is correct
4 Correct 124 ms 1256 KB Output is correct
5 Correct 121 ms 1232 KB Output is correct
6 Correct 129 ms 1348 KB Output is correct
7 Correct 132 ms 1256 KB Output is correct
8 Correct 136 ms 1252 KB Output is correct
9 Correct 144 ms 1256 KB Output is correct
10 Correct 109 ms 1260 KB Output is correct
11 Correct 43 ms 1348 KB Output is correct
12 Correct 73 ms 1348 KB Output is correct
13 Correct 132 ms 1280 KB Output is correct
14 Correct 87 ms 1244 KB Output is correct
15 Correct 95 ms 1260 KB Output is correct
16 Correct 63 ms 1248 KB Output is correct

Subtask #2
0 / 73.0

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