| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 428565 |
2021-06-15T12:54:31 Z |
youngyojun |
색종이 (kriii3_T) |
C++17 |
|
135 ms |
1352 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) (V).begin(),(V).end()
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef pair<ld, ld> pdd;
const ld PI = acos(0)*2;
const ld eps = 1e-12;
bool isZero(const ld &x) { return -eps <= x && x <= eps; }
bool isSame(const ld &a, const ld &b) { return isZero(a-b); }
bool isBet(const ld &a, const ld &b, const ld &c) {
return a-eps <= b && b-eps <= c
|| c-eps <= b && b-eps <= a;
}
bool isBet(const pdd &a, const pdd &b, const pdd &c) {
return isBet(a.fi, b.fi, c.fi)
&& isBet(a.se, b.se, c.se);
}
ld norm(ld theta) {
theta = fmod(theta, PI*2);
while(theta < 0) theta += PI*2;
return theta;
}
bool operator == (const pdd &a, const pdd &b) { return isSame(a.fi, b.fi) && isSame(a.se, b.se); }
bool operator != (const pdd &a, const pdd &b) { return !(a == b); }
pdd operator + (const pdd &a, const pdd &b) { return pdd(a.fi + b.fi, a.se + b.se); }
pdd operator - (const pdd &a, const pdd &b) { return pdd(a.fi - b.fi, a.se - b.se); }
pdd operator * (const pdd &a, const ld &b) { return pdd(a.fi * b, a.se * b); }
pdd operator / (const pdd &a, const ld &b) { return pdd(a.fi / b, a.se / b); }
ld operator * (const pdd &a, const pdd &b) { return a.fi * b.se - a.se * b.fi; }
ld operator / (const pdd &a, const pdd &b) { return a.fi * b.fi + a.se * b.se; }
ld dist2(const pdd &v) { return v/v; }
pdd rotNVec(const ld &theta) { return pdd(cos(theta), sin(theta)); }
ld ccw(const pdd &a, const pdd &b, const pdd &c) { return a*b + b*c + c*a; }
pdd readPdd() {
pdd p;
cin >> p.fi >> p.se;
return p;
}
struct LINE {
LINE(pdd s, pdd e)
: s(s), e(e) {}
pdd s, e;
};
struct TRI {
int idx;
pdd p[3];
void input() {
for(int i = 3; i--;)
p[i] = readPdd();
if(ccw(p[0], p[1], p[2]) <= 0)
swap(p[1], p[2]);
}
};
struct CIR {
int idx;
pdd p;
ld r;
void input() {
p = readPdd();
cin >> r;
}
};
bool isSame(const CIR &a, const CIR &b) {
return a.p == b.p && isSame(a.r, b.r);
}
bool isIn(const CIR &a, const pdd &p) {
return dist2(p - a.p) <= a.r*a.r - eps;
}
bool isIn(const TRI &a, const pdd &p) {
return eps <= ccw(a.p[0], a.p[1], p)
&& eps <= ccw(a.p[1], a.p[2], p)
&& eps <= ccw(a.p[2], a.p[0], p);
}
ld integral(const CIR &cir, const ld &s, const ld &e) {
return cir.p.fi * cir.r * (sin(e) - sin(s))
+ cir.r * cir.r * (e-s + (sin(e+e) - sin(s+s)) / 2) / 2;
}
bool cirInsec(const pdd &p, const ld &r, const ld &R, ld &th1, ld &th2) {
ld d2 = p/p, d = sqrt(d2);
ld cosGamma = (r*r + d2 - R*R) / (r*d*2);
if(cosGamma < -1 || 1 < cosGamma)
return false;
ld gamma = acos(cosGamma);
ld phi = atan2(p.se, p.fi);
th1 = norm(PI + phi - gamma);
th2 = norm(PI + phi + gamma);
if(th1 > th2) swap(th1, th2);
return true;
}
int cirLineInsec(const pdd &p, const ld &r, const pdd &a, const pdd &b
, ld &th1, ld &th2, pdd &sec1, pdd &sec2) {
pdd v = b-a, n(v.se, -v.fi);
ld d = (p-a) / n, nsz = sqrt(n/n);
if(d < 0) {
d = -d;
n = pdd(-n.fi, -n.se);
}
d /= nsz;
ld cosGamma = d / r;
if(cosGamma < 0 || 1 < cosGamma)
return 0;
ld gamma = acos(cosGamma);
ld phi = atan2(n.se, n.fi);
th1 = norm(PI + phi - gamma);
th2 = norm(PI + phi + gamma);
if(th1 > th2) swap(th1, th2);
sec1 = p + rotNVec(th1) * r;
sec2 = p + rotNVec(th2) * r;
bool flag1 = isBet(a, sec1, b);
bool flag2 = isBet(a, sec2, b);
if(flag1)
return flag2 ? 2 : 1;
if(!flag2)
return 0;
swap(th1, th2);
swap(sec1, sec2);
return 1;
}
vector<TRI> TV;
vector<LINE> LV;
vector<CIR> CV;
ld Ans[205][205];
int N;
void solveCir() {
for(const CIR &cir : CV) {
const int idx = cir.idx;
vector<ld> V = {0, PI*2};
for(const CIR &o : CV) if(!isSame(cir, o)) {
ld th1, th2;
if(cirInsec(cir.p - o.p, cir.r, o.r, th1, th2)) {
V.eb(th1);
V.eb(th2);
}
}
for(const LINE &o : LV) {
ld th[2]; pdd sec[2];
int ret = cirLineInsec(cir.p, cir.r, o.s, o.e, th[0], th[1], sec[0], sec[1]);
while(ret--) V.eb(th[ret]);
}
sort(allv(V));
V.erase(unique(allv(V), [&](const ld &a, const ld &b) {
return isSame(a, b);
}), V.end());
int n = sz(V);
for(int i = 1; i < n; i++) {
ld ths = V[i-1], the = V[i];
ld val = integral(cir, ths, the);
pdd cp = cir.p + rotNVec((ths + the) / 2) * cir.r;
int si = 0, ei = N+1;
for(const CIR &o : CV) {
if(si < o.idx && o.idx < idx && !isSame(cir, o) && isIn(o, cp))
si = o.idx;
if(idx < o.idx && o.idx < ei && (isSame(cir, o) || isIn(o, cp)))
ei = o.idx;
}
for(const TRI &o : TV) {
if(si < o.idx && o.idx < idx && isIn(o, cp))
si = o.idx;
if(idx < o.idx && o.idx < ei && isIn(o, cp))
ei = o.idx;
}
for(int i = idx; i < ei; i++) {
Ans[i][idx] += val;
Ans[i][si] -= val;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) {
int t; cin >> t;
if(1 == t) {
TV.eb();
auto &t = TV.back();
t.idx = i;
t.input();
LV.eb(t.p[0], t.p[1]);
LV.eb(t.p[1], t.p[2]);
LV.eb(t.p[2], t.p[0]);
} else {
CV.eb();
CV.back().idx = i;
CV.back().input();
}
}
solveCir();
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= i; j++)
printf("%.15Lf ", Ans[i][j]);
putchar('\n');
}
return 0;
}
Compilation message
paper.cpp: In function 'bool isBet(const ld&, const ld&, const ld&)':
paper.cpp:15:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
15 | return a-eps <= b && b-eps <= c
| ~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
1348 KB |
Output is correct |
| 2 |
Correct |
120 ms |
1256 KB |
Output is correct |
| 3 |
Correct |
131 ms |
1244 KB |
Output is correct |
| 4 |
Correct |
135 ms |
1336 KB |
Output is correct |
| 5 |
Correct |
118 ms |
1348 KB |
Output is correct |
| 6 |
Correct |
129 ms |
1244 KB |
Output is correct |
| 7 |
Correct |
128 ms |
1252 KB |
Output is correct |
| 8 |
Correct |
119 ms |
1348 KB |
Output is correct |
| 9 |
Correct |
102 ms |
1264 KB |
Output is correct |
| 10 |
Correct |
112 ms |
1260 KB |
Output is correct |
| 11 |
Correct |
43 ms |
1348 KB |
Output is correct |
| 12 |
Correct |
52 ms |
1252 KB |
Output is correct |
| 13 |
Correct |
93 ms |
1348 KB |
Output is correct |
| 14 |
Correct |
89 ms |
1352 KB |
Output is correct |
| 15 |
Correct |
98 ms |
1264 KB |
Output is correct |
| 16 |
Correct |
67 ms |
1252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
1304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
