oj.uz

Submission #374106

# Submission time Handle Problem Language Result Execution time Memory
374106 2021-03-06T16:29:14 Z cki86201 색종이 (kriii3_T) C++17
109 / 109
 137 ms 1516 KB 
#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-14;
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 && -EPS <= w && w <= 1 + EPS) 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(-EPS <= t && t <= 1 + EPS) mp[tp++] = get_angle(t);
	if(is_zero(dt)) return tp;
	t = (-b - dt) / a;
	if(-EPS <= t && t <= 1 + EPS) 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) + EPS) return 0;
	if(d2 < (C1.R - C2.R) * (C1.R - C2.R) - EPS) 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) {
		while(x < 0) x += 2 * PI;
		while(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 || VT[j].is_in(pt, vec2) == 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

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

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1388 KB Output is correct
2 Correct 70 ms 1388 KB Output is correct
3 Correct 76 ms 1388 KB Output is correct
4 Correct 74 ms 1388 KB Output is correct
5 Correct 74 ms 1516 KB Output is correct
6 Correct 87 ms 1516 KB Output is correct
7 Correct 74 ms 1388 KB Output is correct
8 Correct 70 ms 1408 KB Output is correct
9 Correct 63 ms 1388 KB Output is correct
10 Correct 66 ms 1388 KB Output is correct
11 Correct 30 ms 1388 KB Output is correct
12 Correct 35 ms 1388 KB Output is correct
13 Correct 66 ms 1516 KB Output is correct
14 Correct 60 ms 1516 KB Output is correct
15 Correct 56 ms 1516 KB Output is correct
16 Correct 41 ms 1388 KB Output is correct

Subtask #2
73.0 / 73.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1388 KB Output is correct
2 Correct 117 ms 1336 KB Output is correct
3 Correct 123 ms 1516 KB Output is correct
4 Correct 127 ms 1388 KB Output is correct
5 Correct 119 ms 1388 KB Output is correct
6 Correct 103 ms 1388 KB Output is correct
7 Correct 105 ms 1388 KB Output is correct
8 Correct 137 ms 1388 KB Output is correct
9 Correct 134 ms 1388 KB Output is correct
10 Correct 117 ms 1388 KB Output is correct
11 Correct 88 ms 1388 KB Output is correct
12 Correct 108 ms 1516 KB Output is correct
13 Correct 54 ms 1388 KB Output is correct
14 Correct 43 ms 1388 KB Output is correct
15 Correct 75 ms 1388 KB Output is correct
16 Correct 92 ms 1388 KB Output is correct
17 Correct 76 ms 1388 KB Output is correct
18 Correct 80 ms 1388 KB Output is correct
19 Correct 79 ms 1388 KB Output is correct
20 Correct 96 ms 1388 KB Output is correct