제출 #376936

#제출 시각아이디문제언어결과실행 시간메모리
376936koioi.org-koosaga색종이 (kriii3_T)C++17
0 / 109
383 ms1652 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); } llf 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; } llf dist() const { return sqrt((llf)dist2()); } // angle to x-axis in interval [-pi, pi] llf 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(llf a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } }; using punk = Point<llf>; const llf eps = 1e-14L; 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; llf r = r1 + r2, d2 = delta.dist2(); llf p = (d2 + (r1 - r2) * (r1 + r2)) / (2.0 * d2); llf h2 = r1*r1 - p*p*d2; if (d2 > r*r + eps || h2 < -eps) 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; 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++){ // if(fabs(witness[i] - witness[i - 1]) < eps) continue; 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 - p1); for(int i = x.idx; i < max_idx; i++){ dx[min_idx + 1][i] += result; dx[x.idx + 1][i] -= result; } } } bool velocity(punk A, punk B, punk C, punk D){ punk X = (B - A).unit(); punk Y = (D - C).unit(); return 1; } 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(fabs(witness[i] - witness[i - 1]) < eps) continue; if(witness[i - 1] < -eps || witness[i] > 1 + eps) continue; llf m = (witness[i - 1] + witness[i]) / 2; auto P = A + (B - A) * witness[i - 1]; auto Q = A + (B - A) * witness[i]; 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){ bool over = false; for(int k = 0; k < 3; k++){ punk X, Y; if(velocity(P, Q, j.p[k], j.p[k + 1]) == 1 && segmentIntersection(P, Q, j.p[k], j.p[k + 1], X, Y) == 2) over = true; } if(!over) 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]); for(int i = x.idx; i < max_idx; i++){ dx[min_idx + 1][i] += result; dx[x.idx + 1][i] -= 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 <= i; j++){ printf("%.20Lf ", 0.5 * -dx[j+1][i]); } puts(""); } }

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

paper.cpp: In function 'bool velocity(punk, punk, punk, punk)':
paper.cpp:197:7: warning: variable 'X' set but not used [-Wunused-but-set-variable]
  197 |  punk X = (B - A).unit();
      |       ^
paper.cpp:198:7: warning: variable 'Y' set but not used [-Wunused-but-set-variable]
  198 |  punk Y = (D - C).unit();
      |       ^
paper.cpp: In function 'int main()':
paper.cpp:281:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  281 |  int n; scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
paper.cpp:286:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  286 |   scanf("%d",&t);
      |   ~~~~~^~~~~~~~~
paper.cpp:293:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  293 |    scanf("%d %d %d",&x,&y,&r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~
In function 'void solve_line(triangle, std::vector<triangle>, std::vector<circle>)':
cc1plus: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
paper.cpp:255:24: note: within this loop
  255 |       for(int k = 0; k < 3; k++){
      |                      ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...