제출 #376432

#제출 시각아이디문제언어결과실행 시간메모리
376432koioi.org-koosaga색종이 (kriii3_T)C++17
0 / 109
294 ms1388 KiB
#include <bits/stdc++.h> using namespace std; using lint = long long; using llf = long double; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() const int MAXN = 205; template<class T> struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } }; using punk = Point<llf>; const llf eps = 1e-9; const llf pi = acos(-1); llf ccw(punk A, punk B, punk C){ return A.cross(B, C); } llf dot(punk A, punk B, punk C){ return (B - A).dot(C - A); } int sgn(llf x){ if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } struct triangle { punk p[3]; int idx; void input(){ for(int j = 0; j < 3; j++){ cin >> p[j].x >> p[j].y; } if(p[0].cross(p[1], p[2]) < 0) swap(p[1], p[2]); } bool in(punk x){ for(int j = 0; j < 3; j++){ if(ccw(p[j], p[(j+1)%3], x) < -eps) return 0; } return 1; } }; struct circle{ punk C; llf r; int idx; bool in(punk x){ return (C - x).dist2() <= r * r + eps; } bool operator!=(const circle &c){ return sgn((c.C - C).dist2()) != 0 || sgn(r - c.r) != 0; } }; template<class P> int segmentIntersection(const P& s1, const P& e1, const P& s2, const P& e2, P& r1, P& r2) { if (e1==s1) { if (e2==s2) { if (e1==e2) { r1 = e1; return 1; } //all equal else return 0; //different point segments } else return segmentIntersection(s2,e2,s1,e1,r1,r2);//swap } //segment directions and separation P v1 = e1-s1, v2 = e2-s2, d = s2-s1; auto a = v1.cross(v2), a1 = v1.cross(d), a2 = v2.cross(d); if (a == 0) { //if parallel auto b1=s1.dot(v1), c1=e1.dot(v1), b2=s2.dot(v1), c2=e2.dot(v1); if (a1 || a2 || max(b1,min(b2,c2))>min(c1,max(b2,c2))) return 0; r1 = min(b2,c2)<b1 ? s1 : (b2<c2 ? s2 : e2); r2 = max(b2,c2)>c1 ? e1 : (b2>c2 ? s2 : e2); return 2-(r1==r2); } if (a < 0) { a = -a; a1 = -a1; a2 = -a2; } if (0<a1 || a<-a1 || 0<a2 || a<-a2) return 0; r1 = s1-v1*a2/a; return 1; } template<class P> bool circleIntersection(P a, P b, llf r1, llf r2, pair<P, P>* out) { P delta = b - a; if(delta.dist2() < eps) return false; double r = r1 + r2, d2 = delta.dist2(); double p = (d2 + r1*r1 - r2*r2) / (2.0 * d2); double h2 = r1*r1 - p*p*d2; if (d2 > r*r || h2 < 0) return false; P mid = a + delta*p, per = delta.perp() * sqrt(h2 / d2); *out = {mid + per, mid - per}; return true; } bool segmentCircle(punk A, punk B, punk C, llf r, punk &X, punk &Y){ llf dis = fabs(ccw(A, B, C)) / (B - A).dist(); if(sgn(dis - r) > 0) return 0; punk M = A + (B - A) * (dot(A, B, C) / (B - A).dist2()); punk D = (B - A).unit() * sqrt(r * r - dis * dis); X = M - D; Y = M + D; return 1; } llf dx[MAXN][MAXN]; void solve_circle(circle x, vector<triangle> t, vector<circle> c){ vector<llf> witness = {0, 2 * pi}; auto ratio = [&](punk C){ C = C - x.C; assert(fabs(C.dist2() - x.r * x.r) < eps); llf ans = atan2l(C.y, C.x); while(ans < 0) ans += 2 * pi; return ans; }; for(auto &i : t){ if(x.idx == i.idx) continue; for(int j = 0; j < 3; j++){ punk C = i.p[j]; punk D = i.p[(j+1)%3]; punk X, Y; if(segmentCircle(C, D, x.C, x.r, X, Y)){ witness.push_back(ratio(X)); witness.push_back(ratio(Y)); } } } for(auto &i : c){ if(x.idx == i.idx) continue; pair<punk, punk> P; if(circleIntersection(i.C, x.C, i.r, x.r, &P)){ witness.push_back(ratio(P.first)); witness.push_back(ratio(P.second)); } } sort(all(witness)); for(int i = 1; i < sz(witness); i++){ llf m = (witness[i - 1] + witness[i]) / 2; punk M = x.C + punk(x.r, 0).rotate(m); int min_idx = -1; int max_idx = sz(t) + sz(c); for(auto &j : t){ if(j.idx == x.idx) continue; if(j.in(M)){ if(j.idx < x.idx) min_idx = max(min_idx, j.idx); else max_idx = min(max_idx, j.idx); } } for(auto &j : c){ if(j.idx == x.idx) continue; if(j.in(M)){ if(j.idx < x.idx){ if(j != x) min_idx = max(min_idx, j.idx); } else max_idx = min(max_idx, j.idx); } } llf theta = witness[i] - witness[i - 1]; punk p1 = punk(1, 0).rotate(witness[i - 1]); punk p2 = punk(1, 0).rotate(witness[i]); llf result = x.r * x.r * theta + x.r * (x.C.cross(p2) - x.C.cross(p1)); // printf("%d %d %d %.10Lf\n", min_idx + 1, x.idx, max_idx - 1, result); dx[min_idx + 1][x.idx] += result; dx[min_idx + 1][max_idx] -= result; dx[x.idx + 1][x.idx] -= result; dx[x.idx + 1][max_idx] += result; } } void solve_line(triangle x, vector<triangle> t, vector<circle> c){ for(int i = 0; i < 3; i++){ punk A = x.p[i]; punk B = x.p[(i+1)%3]; vector<llf> witness = {0, 1}; auto ratio = [&](punk C){ if(sgn(A.x - B.x) == 0) return (C.y - A.y) / (B.y - A.y); return (C.x - A.x) / (B.x - A.x); }; for(auto &i : t){ if(x.idx == i.idx) continue; for(int j = 0; j < 3; j++){ punk C = i.p[j]; punk D = i.p[(j+1)%3]; if(sgn(ccw(A, B, C)) == 0 && sgn(ccw(A, B, D)) == 0){ witness.push_back(ratio(C)); witness.push_back(ratio(D)); } else{ punk X, Y; int val = segmentIntersection(A, B, C, D, X, Y); assert(val != 2); if(val){ llf r = ratio(X); witness.push_back(r); } } } } for(auto &i : c){ punk P, Q; if(segmentCircle(A, B, i.C, i.r, P, Q)){ llf r1 = ratio(P), r2 = ratio(Q); if(r1 > r2) swap(r1, r2); witness.push_back(r1); witness.push_back(r2); } } sort(all(witness)); for(int i = 1; i < sz(witness); i++){ if(witness[i - 1] < -eps || witness[i] > 1 + eps) continue; llf m = (witness[i - 1] + witness[i]) / 2; auto M = A + (B - A) * m; int min_idx = -1; int max_idx = sz(t) + sz(c); for(auto &j : t){ if(j.idx == x.idx) continue; if(j.in(M)){ if(j.idx < x.idx) min_idx = max(min_idx, j.idx); else max_idx = min(max_idx, j.idx); } } for(auto &j : c){ if(j.idx == x.idx) continue; if(j.in(M)){ if(j.idx < x.idx) min_idx = max(min_idx, j.idx); else max_idx = min(max_idx, j.idx); } } llf result = A.cross(B) * (witness[i] - witness[i - 1]); dx[min_idx + 1][x.idx] += result; dx[min_idx + 1][max_idx] -= result; dx[x.idx + 1][x.idx] -= result; dx[x.idx + 1][max_idx] += result; } } } int main(){ int n; scanf("%d",&n); vector<triangle> vt; vector<circle> vc; for(int i = 0; i < n; i++){ int t; scanf("%d",&t); if(t == 1){ triangle c; c.input(); vt.push_back(c); vt.back().idx = i; } else { int x, y, r; scanf("%d %d %d",&x,&y,&r); vc.push_back({punk(x, y), llf(r)}); vc.back().idx = i; } } for(auto &i : vt) solve_line(i, vt, vc); for(auto &i : vc) solve_circle(i, vt, vc); for(int i = 0; i <= n; i++){ for(int j = 0; j <= n; j++){ if(i) dx[i][j] += dx[i-1][j]; if(j) dx[i][j] += dx[i][j-1]; if(i&&j) dx[i][j] -= dx[i-1][j-1]; } } for(int i = 0; i < n; i++){ for(int j = 0; j <= i; j++){ printf("%.10Lf ", 0.5 * (dx[j][i] - dx[j + 1][i])); } puts(""); } }

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

paper.cpp: In function 'int main()':
paper.cpp:266:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  266 |  int n; scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
paper.cpp:271:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  271 |   scanf("%d",&t);
      |   ~~~~~^~~~~~~~~
paper.cpp:278:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  278 |    scanf("%d %d %d",&x,&y,&r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...