Submission #374090

#	Time	Username	Problem	Language	Result	Execution time	Memory
374090		cki86201	색종이 (kriii3_T)	C++17	36 / 109	130 ms	1516 KiB

paper

#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

using FL = long double;
const FL EPS = 1e-11;
const FL NIL = 12345;
const FL PI = acosl(-1);
inline bool is_zero(FL x) { return -EPS <= x && x <= EPS; }

int N;

struct point {
	point() {}
	point(FL x, FL y) : x(x), y(y) {}
	FL x, y;
	point operator-(const point &p) const { return {x - p.x, y - p.y}; }
	point operator+(const point &p) const { return {x + p.x, y + p.y}; }
	point operator*(FL a) const { return {x * a, y * a}; }
	FL operator*(const point &p) const { return x * p.x + y * p.y; }
	FL operator/(const point &p) const { return x * p.y - y * p.x; }
	FL len2() { return x * x + y * y; }
	FL length() { return sqrt(x * x + y * y); }
	FL angle() { return atan2(y, x); }
	point rot90() { return {y, -x}; }
};

struct line {
	line(point s, point e) : s(s), e(e) {}
	point s, e;
};

struct triangle {
	point p1, p2, p3;
	int id;
	int is_in(point P, point V) {
		FL v1 = (p2 - p1) / (P - p1);
		if(v1 > EPS) return 0;
		FL v2 = (p3 - p2) / (P - p2);
		if(v2 > EPS) return 0;
		FL v3 = (p1 - p3) / (P - p3);
		if(v3 > EPS) return 0;
		if(is_zero(v1)) return V / (p2 - p1) > 0 ? 2 : 0;
		if(is_zero(v2)) return V / (p3 - p2) > 0 ? 2 : 0;
		if(is_zero(v3)) return V / (p1 - p3) > 0 ? 2 : 0;
		return 1;
	}
};

struct circle {
	point C;
	int R, id;
	int is_in(point P) {
		FL v1 = (P - C).len2();
		return v1 <= R * R;
	}
	FL get_angle(point P) {
		FL v = atan2(P.y - C.y, P.x - C.x);
		if(v < 0) v += 2 * PI;
		return v;
	}
	point get_point(FL t) {
		FL x = C.x + R * cos(t);
		FL y = C.y + R * sin(t);
		return {x, y};
	}
	FL get_area(FL ts, FL te) {
		FL v1 = R * R * (FL)0.5 * ((te - ts) - (FL)0.5 * (sin(te * 2) - sin(ts * 2)));
		v1 -= R * C.y * (cos(te) - cos(ts));
		return v1;
	}
	int same(const circle &m) {
		return C.x == m.C.x && C.y == m.C.y && R == m.R;
	}
};

vector <triangle> VT;
vector <circle> VC;

FL ans[210][210];

FL meetll(line L1, line L2) {
	if(is_zero((L1.e - L1.s) / (L2.e - L2.s))) return NIL;
	FL v = ((L2.s - L1.s) / (L2.e - L2.s)) / ((L1.e - L1.s) / (L2.e - L2.s));
	FL w = ((L1.s - L2.s) / (L1.e - L1.s)) / ((L2.e - L2.s) / (L1.e - L1.s));
	if(0 <= v && v <= 1 && 0 <= w && w <= 1) return v;
	return NIL;
}

int meetlc(line L, circle C, FL mp[]) {
	FL a = (L.e - L.s).len2();
	FL b = (L.e - L.s) * (L.s - C.C);
	FL c = (L.s - C.C).len2() - C.R * C.R;
	FL det = b * b - a * c;
	if(det < -EPS) return 0;
	FL dt = sqrt(max((FL)0, det));
	FL t = (-b + dt) / a;
	int tp = 0;
	if(0 <= t && t <= 1) mp[tp++] = t;
	if(is_zero(dt)) return tp;
	t = (-b - dt) / a;
	if(0 <= t && t <= 1) mp[tp++] = t;
	return tp;
}

int meetcl(circle C, line L, FL mp[]) {
	FL a = (L.e - L.s).len2();
	FL b = (L.e - L.s) * (L.s - C.C);
	FL c = (L.s - C.C).len2() - C.R * C.R;
	FL det = b * b - a * c;
	if(det < -EPS) return 0;
	auto get_angle = [&](FL t) {
		return C.get_angle(L.s + (L.e - L.s) * t);
	};
	FL dt = sqrt(max((FL)0, det));
	FL t = (-b + dt) / a;
	int tp = 0;
	if(0 <= t && t <= 1) mp[tp++] = get_angle(t);
	if(is_zero(dt)) return tp;
	t = (-b - dt) / a;
	if(0 <= t && t <= 1) mp[tp++] = get_angle(t);
	return tp;
}

int meetcc(circle C1, circle C2, FL mp[]) {
	FL d2 = (C2.C - C1.C).len2();
	if(d2 > (C1.R + C2.R) * (C1.R + C2.R)) return 0;
	if(d2 < (C1.R - C2.R) * (C1.R - C2.R)) return 0;
	FL ct = (C2.C - C1.C).angle();
	FL temp = (C1.R * C1.R + d2 - C2.R * C2.R) / (2 * C1.R * sqrt(d2));
	if(temp < -1) temp = -1;
	if(temp > 1) temp = 1;
	auto fix = [&](FL &x) {
		if(x < 0) x += 2 * PI;
		if(x >= 2 * PI) x -= 2 * PI;
	};
	FL dt = acos(temp);
	int tp = 0;
	FL v1 = ct + dt;
	fix(v1);
	mp[tp++] = v1;
	if(is_zero(dt)) return tp;
	v1 = ct - dt;
	fix(v1);
	mp[tp++] = v1;
	return tp;
}

void solveL(line L, int id) {
	if(L.s.x == L.e.x) return;
	vector <FL> vx = {0, 1};
	for(auto t : VT) {
		if(t.id == id) continue;
		FL x = meetll(L, line(t.p1, t.p2));
		if(x != NIL) vx.pb(x);
		x = meetll(L, line(t.p2, t.p3));
		if(x != NIL) vx.pb(x);
		x = meetll(L, line(t.p3, t.p1));
		if(x != NIL) vx.pb(x);
	}
	for(auto c : VC) {
		FL mp[2];
		int lm = meetlc(L, c, mp);
		rep(i, lm) vx.pb(mp[i]);
	}
	sort(all(vx));
	int m = szz(vx);
	point vec1 = (L.e - L.s).rot90();
	point vec2 = vec1 * (-1);

	int t_idx = 0, c_idx = 0;
	while(t_idx < szz(VT) && VT[t_idx].id < id) ++t_idx;
	while(c_idx < szz(VC) && VC[c_idx].id < id) ++c_idx;
	rep(i, m-1) {
		if(is_zero(vx[i] - vx[i+1])) continue;
		FL t2 = (vx[i] + vx[i+1]) * 0.5;
		point pt = L.s + (L.e - L.s) * t2;
		int prv = -1, nxt1 = N + 1, nxt2 = N + 1, co = -1;

		for(int j=t_idx-1;j>=0;j--) {
			int w = VT[j].is_in(pt, vec1);
			if(w == 2) co = max(co, VT[j].id);
			if(w) {
				prv = max(prv, VT[j].id);
				break;
			}
		}
		for(int j=c_idx-1;j>=0;j--) {
			if(VC[j].is_in(pt)) {
				prv = max(prv, VC[j].id);
				break;
			}
		}

		for(int j=t_idx;j<szz(VT);j++) {
			if(VT[j].id == id) continue;
			if(VT[j].is_in(pt, vec1)) {
				nxt1 = min(nxt1, VT[j].id);
			}
			if(VT[j].is_in(pt, vec2)) {
				nxt2 = min(nxt2, VT[j].id);
			}
			if(nxt1 <= N && nxt2 <= N) break;
		}
		for(int j=c_idx;j<szz(VC);j++) {
			if(VC[j].is_in(pt)) {
				nxt1 = min(nxt1, VC[j].id);
				nxt2 = min(nxt2, VC[j].id);
			}
		}

		FL area = pt.y * (vx[i+1] - vx[i]) * (L.e.x - L.s.x);

		if(prv != -1 && prv > co) {
			for(int a=id;a<nxt2;a++) {
				ans[a][prv] -= area;
			}
		}

		for(int a=id;a<nxt1;a++) {
			ans[a][id] += area;
		}
	}
}

void solveC(circle C) {
	int id = C.id;
	vector <FL> vx = {0, 2 * PI};
	for(auto t : VT) {
		FL mp[6];
		int tp = 0;
		tp += meetcl(C, {t.p1, t.p2}, mp + tp);
		tp += meetcl(C, {t.p2, t.p3}, mp + tp);
		tp += meetcl(C, {t.p3, t.p1}, mp + tp);
		rep(i, tp) vx.pb(mp[i]);
	}
	for(auto c : VC) {
		if(c.id == id || c.same(C)) continue;
		FL mp[2];
		int tp = meetcc(C, c, mp);
		rep(i, tp) vx.pb(mp[i]);
	}
	sort(all(vx));
	int m = szz(vx);

	int t_idx = 0, c_idx = 0;
	while(t_idx < szz(VT) && VT[t_idx].id < id) ++t_idx;
	while(c_idx < szz(VC) && VC[c_idx].id < id) ++c_idx;
	rep(i, m-1) {
		FL t = (vx[i] + vx[i+1]) * 0.5;
		if(is_zero(vx[i] - vx[i+1])) continue;

		point pt = C.get_point(t), vec = C.C - pt;
		int prv = -1, nxt = N + 1;

		for(int j=t_idx-1;j>=0;j--) {
			if(VT[j].is_in(pt, vec)) {
				prv = VT[j].id;
				break;
			}
		}
		for(int j=c_idx-1;j>=0;j--) {
			if(VC[j].same(C)) continue;
			if(VC[j].is_in(pt)) {
				prv = max(prv, VC[j].id);
				break;
			}
		}

		for(int j=t_idx;j<szz(VT);j++) {
			if(VT[j].is_in(pt, vec)) {
				nxt = VT[j].id;
				break;
			}
		}
		for(int j=c_idx;j<szz(VC);j++) {
			if(VC[j].id == id) continue;
			if(VC[j].same(C) || VC[j].is_in(pt)) {
				nxt = min(nxt, VC[j].id);
				break;
			}
		}

		FL area = C.get_area(vx[i], vx[i+1]);

		if(prv != -1) {
			for(int a=id;a<nxt;a++) {
				ans[a][prv] -= area;
			}
		}

		for(int a=id;a<nxt;a++) {
			ans[a][id] += area;
		}
	}
}

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int tp; scanf("%d", &tp);
		if(tp == 2) {
			int x, y, r;
			scanf("%d%d%d", &x, &y, &r);
			circle c;
			c.id = i, c.R = r;
			c.C = point(x, y);
			VC.pb(c);
		}
		else {
			int x1, y1, x2, y2, x3, y3;
			scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
			point p1 = point(x1, y1);
			point p2 = point(x2, y2);
			point p3 = point(x3, y3);
			if((p2-p1) / (p3-p2) > 0) swap(p2, p3);
			triangle t;
			t.id = i, t.p1 = p1;
			t.p2 = p2, t.p3 = p3;
			VT.pb(t);
		}
	}
	for(triangle t : VT) {
		solveL({t.p1, t.p2}, t.id);
		solveL({t.p2, t.p3}, t.id);
		solveL({t.p3, t.p1}, t.id);
	}
	for(circle c : VC) solveC(c);

	for(int i=1;i<=N;i++) {
		for(int j=1;j<=i;j++) printf("%.15Lf ", ans[i][j]);
		puts("");
	}
	return 0;
}

Compilation message (stderr)

paper.cpp: In function 'int main()':
paper.cpp:309:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  309 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
paper.cpp:311:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  311 |   int tp; scanf("%d", &tp);
      |           ~~~~~^~~~~~~~~~~
paper.cpp:314:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  314 |    scanf("%d%d%d", &x, &y, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paper.cpp:322:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  322 |    scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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