Submission #428797

#	Time	Username	Problem	Language	Result	Execution time	Memory
428797		youngyojun	색종이 (kriii3_T)	C++17	109 / 109	865 ms	1484 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-10;
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; }
bool isSameDir(const pdd &a, const pdd &b, const pdd &c, const pdd &d) {
	return sqrt(dist2(b-a)) + sqrt(dist2(d-c)) < sqrt(dist2(d-a));
}

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

struct LINE {
	LINE(int idx, pdd s, pdd e)
		: idx(idx), s(s), e(e) {}
	int idx;
	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);
}

bool onTri(const TRI &a, const pdd &p, const pdd &s, const pdd &e) {
	return isBet(a.p[0], p, a.p[1]) && isZero(ccw(a.p[0], a.p[1], p)) && isSameDir(a.p[0], s, e, a.p[1])
		|| isBet(a.p[1], p, a.p[2]) && isZero(ccw(a.p[1], a.p[2], p)) && isSameDir(a.p[1], s, e, a.p[2])
		|| isBet(a.p[2], p, a.p[0]) && isZero(ccw(a.p[2], a.p[0], p)) && isSameDir(a.p[2], s, e, a.p[0]);
}

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

ld integral(const pdd &s, const pdd &e) {
	return (e.se - s.se) * (s.fi + e.fi) / 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;
}

int lineInsec(const pdd &a, const pdd &b, const pdd &c, const pdd &d, pdd &sec1, pdd &sec2) {
	pdd v = b-a, u = d-c;
	if(isZero(u*v)) {
		if(!isZero(ccw(a, b, c)))
			return 0;

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

		if(flag1)
			return flag2 ? 2 : 1;

		if(!flag2)
			return 0;

		swap(sec1, sec2);
		return 1;
	}

	pdd n(v.se, -v.fi);
	ld r = ((a-c)/n) / (u/n);

	sec1 = c + u * r;

	return isBet(a, sec1, b) && isBet(c, sec1, d) && isZero(ccw(a, b, sec1)) ? 1 : 0;
}

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

void solveLine() {
	for(const LINE &line : LV) {
		const int idx = line.idx;

		vector<pdd> V = {line.s, line.e};

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

		for(const LINE &o : LV) {
			pdd sec[2];
			int ret = lineInsec(line.s, line.e, o.s, o.e, sec[0], sec[1]);
			while(ret--) V.eb(sec[ret]);
		}

		{
			const pdd v = line.e - line.s;
			for(auto &v : V) v = v - line.s;
			const pdd n(-v.se, v.fi);
			for(auto &v : V) v = v - (n * ((v/n) / sqrt(n/n)));
			sort(allv(V), [&](const pdd &a, const pdd &b) {
				return a/v < b/v;
			});
			V.erase(unique(allv(V), [&](const pdd &a, const pdd &b) {
				return a == b;
			}), V.end());
			for(auto &v : V) v = v + line.s;
		}

		int n = sz(V);
		for(int i = 1; i < n; i++) {
			pdd s = V[i-1], e = V[i], cp = (s+e) * 0.5;
			ld val = integral(s, e);

			int si = 0, ei = N+1;

			for(const CIR &o : CV) {
				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(const TRI &o : TV) {
				if(si < o.idx && o.idx < idx && !onTri(o, cp, s, e) && isIn(o, cp))
					si = o.idx;
				if(idx < o.idx && o.idx < ei && (onTri(o, cp, s, e) || 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(i, t.p[0], t.p[1]);
			LV.eb(i, t.p[1], t.p[2]);
			LV.eb(i, t.p[2], t.p[0]);
		} else {
			CV.eb();
			CV.back().idx = i;
			CV.back().input();
		}
	}

	solveCir();
	solveLine();

	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 (stderr)

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
      |         ~~~~~~~~~~~^~~~~~~~~~~~~
paper.cpp: In function 'bool onTri(const TRI&, const pdd&, const pdd&, const pdd&)':
paper.cpp:95:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   95 |  return isBet(a.p[0], p, a.p[1]) && isZero(ccw(a.p[0], a.p[1], p)) && isSameDir(a.p[0], s, e, a.p[1])
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paper.cpp:97:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |   || isBet(a.p[2], p, a.p[0]) && isZero(ccw(a.p[2], a.p[0], p)) && isSameDir(a.p[2], s, e, a.p[0]);
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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