제출 #15474

#제출 시각아이디문제언어결과실행 시간메모리
15474myungwoo색종이 (kriii3_T)C++14
0 / 109
1000 ms2688 KiB
#pragma warning(disable:4996) #include <stdio.h> #include <vector> #include <algorithm> #include <set> using namespace std; struct point { double x, y, z; point(){} point(double x, double y, double z=1) : x(x), y(y), z(z) {} double dot(const point& r) const { return x*r.x + y*r.y; } double size() const { return sqrt(x*x + y*y); } double angle() const { return atan2(y, x); } point proj() const { return point(x/z, y/z); } point operator - (const point& r) const { return point(x-r.x, y-r.y); } point operator + (const point& r) const { return point(x+r.x, y+r.y); } point operator * (const double& r) const { return point(x*r, y*r); } point operator * (const point& r) const { return point(y*r.z - z*r.y, z*r.x - x*r.z, x*r.y - y*r.x); } }; int n; point v[200][3]; double r[200]; double sum[200][200]; vector<double> x; void int_cc(point p1, double r1, point p2, double r2) { if (r1 > r2) { int_cc(p2, r2, p1, r1); return; } double d = (p2-p1).size(); if (r1+r2 < d || r2 - r1 > d) return; double t = (p2-p1).angle(); double dt = acos( (r1*r1 + d*d - r2*r2) / (2*r1*d) ); point i1 = p1 + point(r1 * cos(t+dt), r1 * sin(t+dt)); point i2 = p1 + point(r1 * cos(t-dt), r1 * sin(t-dt)); x.push_back(i1.x); x.push_back(i2.x); } void int_cl(point p1, double r1, point p21, point p22) { // l: (1-t)p21 + tp22 = t(p22-p21) + p21 // (p1 - p21 - t(p22-p21))^2 = r1^2 // t^2 (p22-p21)^2 - 2t(p22-p21)(p1-p21) + (p1-p21)^2 - r1^2 = 0 double a = (p22-p21).dot(p22-p21); double b = -(p22-p21).dot(p1-p21); double c = (p1-p21).dot(p1-p21) - r1*r1; double D = b*b - a*c; if (D<0) return; double t1 = (-b + sqrt(D)) / a; double t2 = (-b - sqrt(D)) / a; point i1 = p21 + (p22 - p21) * t1; point i2 = p21 + (p22 - p21) * t2; if (0<=t1 && t1<=1) x.push_back(i1.x); if (0<=t2 && t2<=1) x.push_back(i2.x); } void int_ct(point p1, double r1, point p2[]) { for (int i=0; i<3; i++) int_cl(p1, r1, p2[i], p2[(i+1)%3]); } bool inBox(point x, point b1, point b2) { return min(b1.x, b2.x) <= x.x && x.x <= max(b1.x, b2.x) && min(b1.y, b2.y) <= x.y && x.y <= max(b1.y, b2.y) ; } void int_ll(point p11, point p12, point p21, point p22) { point l1(p11 * p12); point l2(p11 * p12); point i = l1 * l2; if (fabs(i.z) > 1e-4) { i = i.proj(); if (inBox(i, p11, p12) && inBox(i, p21, p22)) x.push_back(i.x); } } void int_tt(point p1[], point p2[]) { for (int i=0; i<3; i++) for (int j=0; j<3; j++) int_ll(p1[i], p1[(i+1)%3], p2[j], p2[(j+1)%3]); } double eval_c(point p, double r, int dir, double x) { // (px - x)^2 + (py - y)^2 = r^2 // py - y = +- sqrt(r^2 - dx^2) // y = py +- sqrt(r^2 - dx^2) double dx = x - p.x; double D = r*r - dx*dx; if (D<0) D = 0; return dir == 1 ? p.y + sqrt(D) : p.y - sqrt(D); } double eval_t(point p[], int dir, double x) { bool f = false; double y = 0.; for (int i=0; i<3; i++) { point p1 = p[i]; point p2 = p[(i+1)%3]; if (min(p1.x, p2.x) <= x && x <= max(p1.x, p2.x)) { double ny = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x); if (!f) { f = true; y = ny; } if (dir == 1 && y < ny) y = ny; if (dir == -1 && y > ny) y = ny; } } return y; } double area_c(point p, double r, int dir, double x1, double x2) { double t1 = acos((x1-p.x) / r); double t2 = acos((x2-p.x) / r); double i = r*r/4 * (sin(2*t2) - sin(2*t1)) - r*r/2 * (t2-t1); return (x2-x1) * p.y + dir * i; } double area_t(point p[], int dir, double x1, double x2) { bool f = false; double y = 0.; int id = -1; double x = (x1+x2)/2; for (int i=0; i<3; i++) { point p1 = p[i]; point p2 = p[(i+1)%3]; if (min(p1.x, p2.x) <= x && x <= max(p1.x, p2.x)) { double ny = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x); if (!f) { f = true; y = ny, id = i; } if (dir == 1 && y < ny) y = ny, id = i; if (dir == -1 && y > ny) y = ny, id = i; } } point p1 = p[id]; point p2 = p[(id+1)%3]; double y1 = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x1 - p1.x); double y2 = p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x2 - p1.x); return (y1+y2)/2 * (x2-x1); } struct segment { int i, dir; double x, y; segment(int i, int dir, double x) : i(i), dir(dir), x(x) { if (r[i]) y = eval_c(v[i][0], r[i], dir, x); else y = eval_t(v[i], dir, x); } bool operator < (const segment& rhs) const { return y < rhs.y; } }; void solve(double x1, double x2) { double x = (x1+x2)/2; vector<segment> s; for (int i=0; i<n; i++) { if (r[i]) { if (v[i][0].x - r[i] <= x && x <= v[i][0].x + r[i]) { s.push_back(segment(i, -1, x)); s.push_back(segment(i, +1, x)); } } else { if (min(v[i][0].x, min(v[i][1].x, v[i][2].x)) <= x && x <= max(v[i][0].x, max(v[i][1].x, v[i][2].x))) { s.push_back(segment(i, -1, x)); s.push_back(segment(i, +1, x)); } } } sort(s.begin(), s.end()); set<int> l; for (int i=0; i<s.size()-1; i++) { double a; if (r[ s[i+1].i ]) a = area_c(v[s[i+1].i][0], r[s[i+1].i], s[i+1].dir, x1, x2); else a = area_t(v[s[i+1].i], s[i+1].dir, x1, x2); if (r[ s[i].i ]) a -= area_c(v[s[i].i][0], r[s[i].i], s[i].dir, x1, x2); else a -= area_t(v[s[i].i], s[i].dir, x1, x2); if (s[i].dir == -1) l.insert(s[i].i); else l.erase(s[i].i); /* int prev = -1; for (int v : l) { if (prev != -1) sum[v][prev] -= a; sum[v][v] += a; prev = v; }*/ } } int main() { scanf("%d", &n); for (int i=0; i<n; i++) { int t; scanf("%d", &t); if (t==1) { double x1, y1, x2, y2, x3, y3; scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3); v[i][0] = point(x1, y1); v[i][1] = point(x2, y2); v[i][2] = point(x3, y3); } else { double x, y, rr; scanf("%lf%lf%lf", &x, &y, &rr); v[i][0] = point(x, y); r[i] = rr; } } for (int i=0; i<n; i++) { if (r[i]) { x.push_back(v[i][0].x - r[i]); x.push_back(v[i][0].x + r[i]); } else { for (int j=0; j<3; j++) x.push_back(v[i][j].x); } } for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) { if (r[i] && r[j]) int_cc(v[i][0], r[i], v[j][0], r[j]); else if (r[i]) int_ct(v[i][0], r[i], v[j]); else if (r[j]) int_ct(v[j][0], r[j], v[i]); else int_tt(v[i], v[j]); } sort(x.begin(), x.end()); x.resize( unique(x.begin(), x.end()) - x.begin() ); for (int i=0; i<x.size()-1; i++) solve(x[i], x[i+1]); for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) sum[j][i] += sum[j-1][i]; for (int i=0; i<n; i++) { for (int j=0; j<=i; j++) printf("%.15lf ", sum[i][j]); printf("\n"); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...