Submission #428565

# Submission time Handle Problem Language Result Execution time Memory
428565 2021-06-15T12:54:31 Z youngyojun 색종이 (kriii3_T) C++17
36 / 109
135 ms 1352 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); }
bool isBet(const ld &a, const ld &b, const ld &c) {
	return a-eps <= b && b-eps <= c
		|| c-eps <= b && b-eps <= a;
}
bool isBet(const pdd &a, const pdd &b, const pdd &c) {
	return isBet(a.fi, b.fi, c.fi)
		&& isBet(a.se, b.se, c.se);
}
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 {
	int idx;

	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;
}

bool isIn(const TRI &a, const pdd &p) {
	return eps <= ccw(a.p[0], a.p[1], p)
		&& eps <= ccw(a.p[1], a.p[2], p)
		&& eps <= ccw(a.p[2], a.p[0], p);
}

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;
}

int cirLineInsec(const pdd &p, const ld &r, const pdd &a, const pdd &b
				, ld &th1, ld &th2, pdd &sec1, pdd &sec2) {
	pdd v = b-a, n(v.se, -v.fi);
	ld d = (p-a) / n, nsz = sqrt(n/n);
	if(d < 0) {
		d = -d;
		n = pdd(-n.fi, -n.se);
	}
	d /= nsz;

	ld cosGamma = d / r;
	if(cosGamma < 0 || 1 < cosGamma)
		return 0;
	
	ld gamma = acos(cosGamma);
	ld phi = atan2(n.se, n.fi);

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

	sec1 = p + rotNVec(th1) * r;
	sec2 = p + rotNVec(th2) * r;

	bool flag1 = isBet(a, sec1, b);
	bool flag2 = isBet(a, sec2, b);

	if(flag1)
		return flag2 ? 2 : 1;
	
	if(!flag2)
		return 0;
	
	swap(th1, th2);
	swap(sec1, sec2);
	return 1;
}

vector<TRI> TV;
vector<LINE> LV;
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);
			}
		}

		for(const LINE &o : LV) {
			ld th[2]; pdd sec[2];
			int ret = cirLineInsec(cir.p, cir.r, o.s, o.e, th[0], th[1], sec[0], sec[1]);
			while(ret--) V.eb(th[ret]);
		}

		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 && !isSame(cir, o) && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && (isSame(cir, o) || isIn(o, cp)))
					ei = o.idx;
			}

			for(const TRI &o : TV) {
				if(si < o.idx && o.idx < idx && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && 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) {
			TV.eb();
			auto &t = TV.back();
			t.idx = i;
			t.input();

			LV.eb(t.p[0], t.p[1]);
			LV.eb(t.p[1], t.p[2]);
			LV.eb(t.p[2], t.p[0]);
		} 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;
}

Compilation message

paper.cpp: In function 'bool isBet(const ld&, const ld&, const ld&)':
paper.cpp:15:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |  return a-eps <= b && b-eps <= c
      |         ~~~~~~~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 122 ms 1348 KB Output is correct
2 Correct 120 ms 1256 KB Output is correct
3 Correct 131 ms 1244 KB Output is correct
4 Correct 135 ms 1336 KB Output is correct
5 Correct 118 ms 1348 KB Output is correct
6 Correct 129 ms 1244 KB Output is correct
7 Correct 128 ms 1252 KB Output is correct
8 Correct 119 ms 1348 KB Output is correct
9 Correct 102 ms 1264 KB Output is correct
10 Correct 112 ms 1260 KB Output is correct
11 Correct 43 ms 1348 KB Output is correct
12 Correct 52 ms 1252 KB Output is correct
13 Correct 93 ms 1348 KB Output is correct
14 Correct 89 ms 1352 KB Output is correct
15 Correct 98 ms 1264 KB Output is correct
16 Correct 67 ms 1252 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 1304 KB Output isn't correct
2 Halted 0 ms 0 KB -