| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 374095 |
2021-03-06T15:33:14 Z |
cki86201 |
색종이 (kriii3_T) |
C++17 |
|
129 ms |
1644 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-11;
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) 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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
74 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
90 ms |
1516 KB |
Output is correct |
| 4 |
Correct |
73 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
72 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
79 ms |
1644 KB |
Output is correct |
| 7 |
Correct |
78 ms |
1516 KB |
Output is correct |
| 8 |
Correct |
77 ms |
1452 KB |
Output is correct |
| 9 |
Correct |
65 ms |
1388 KB |
Output is correct |
| 10 |
Correct |
67 ms |
1388 KB |
Output is correct |
| 11 |
Correct |
30 ms |
1388 KB |
Output is correct |
| 12 |
Correct |
36 ms |
1388 KB |
Output is correct |
| 13 |
Correct |
58 ms |
1388 KB |
Output is correct |
| 14 |
Correct |
57 ms |
1388 KB |
Output is correct |
| 15 |
Correct |
67 ms |
1388 KB |
Output is correct |
| 16 |
Correct |
42 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
119 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
125 ms |
1388 KB |
Output is correct |
| 4 |
Incorrect |
129 ms |
1404 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
