제출 #374079

#제출 시각아이디문제언어결과실행 시간메모리
374079cki86201색종이 (kriii3_T)C++17
36 / 109
40 ms1152 KiB
#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 = double; const FL EPS = 1e-9; 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 < 0) return 0; FL dt = sqrt(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 < 0) return 0; auto get_angle = [&](FL t) { return C.get_angle(L.s + (L.e - L.s) * t); }; FL dt = sqrt(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 = 0; if(w) { 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 = VT[j].id; } if(VT[j].is_in(pt, vec2)) { 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 && 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("%.15f ", ans[i][j]); puts(""); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

paper.cpp: In function 'int main()':
paper.cpp:308:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  308 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
paper.cpp:310:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  310 |   int tp; scanf("%d", &tp);
      |           ~~~~~^~~~~~~~~~~
paper.cpp:313:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  313 |    scanf("%d%d%d", &x, &y, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paper.cpp:321:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  321 |    scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...