| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 428797 |
2021-06-15T14:34:21 Z |
youngyojun |
색종이 (kriii3_T) |
C++17 |
|
865 ms |
1484 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-10;
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; }
bool isSameDir(const pdd &a, const pdd &b, const pdd &c, const pdd &d) {
return sqrt(dist2(b-a)) + sqrt(dist2(d-c)) < sqrt(dist2(d-a));
}
pdd readPdd() {
pdd p;
cin >> p.fi >> p.se;
return p;
}
struct LINE {
LINE(int idx, pdd s, pdd e)
: idx(idx), s(s), e(e) {}
int idx;
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);
}
bool onTri(const TRI &a, const pdd &p, const pdd &s, const pdd &e) {
return isBet(a.p[0], p, a.p[1]) && isZero(ccw(a.p[0], a.p[1], p)) && isSameDir(a.p[0], s, e, a.p[1])
|| isBet(a.p[1], p, a.p[2]) && isZero(ccw(a.p[1], a.p[2], p)) && isSameDir(a.p[1], s, e, a.p[2])
|| isBet(a.p[2], p, a.p[0]) && isZero(ccw(a.p[2], a.p[0], p)) && isSameDir(a.p[2], s, e, a.p[0]);
}
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;
}
ld integral(const pdd &s, const pdd &e) {
return (e.se - s.se) * (s.fi + e.fi) / 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;
}
int lineInsec(const pdd &a, const pdd &b, const pdd &c, const pdd &d, pdd &sec1, pdd &sec2) {
pdd v = b-a, u = d-c;
if(isZero(u*v)) {
if(!isZero(ccw(a, b, c)))
return 0;
sec1 = c; sec2 = d;
bool flag1 = isBet(a, c, b);
bool flag2 = isBet(a, d, b);
if(flag1)
return flag2 ? 2 : 1;
if(!flag2)
return 0;
swap(sec1, sec2);
return 1;
}
pdd n(v.se, -v.fi);
ld r = ((a-c)/n) / (u/n);
sec1 = c + u * r;
return isBet(a, sec1, b) && isBet(c, sec1, d) && isZero(ccw(a, b, sec1)) ? 1 : 0;
}
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;
}
}
}
}
void solveLine() {
for(const LINE &line : LV) {
const int idx = line.idx;
vector<pdd> V = {line.s, line.e};
for(const CIR &o : CV) {
ld th[2]; pdd sec[2];
int ret = cirLineInsec(o.p, o.r, line.s, line.e, th[0], th[1], sec[0], sec[1]);
while(ret--) V.eb(sec[ret]);
}
for(const LINE &o : LV) {
pdd sec[2];
int ret = lineInsec(line.s, line.e, o.s, o.e, sec[0], sec[1]);
while(ret--) V.eb(sec[ret]);
}
{
const pdd v = line.e - line.s;
for(auto &v : V) v = v - line.s;
const pdd n(-v.se, v.fi);
for(auto &v : V) v = v - (n * ((v/n) / sqrt(n/n)));
sort(allv(V), [&](const pdd &a, const pdd &b) {
return a/v < b/v;
});
V.erase(unique(allv(V), [&](const pdd &a, const pdd &b) {
return a == b;
}), V.end());
for(auto &v : V) v = v + line.s;
}
int n = sz(V);
for(int i = 1; i < n; i++) {
pdd s = V[i-1], e = V[i], cp = (s+e) * 0.5;
ld val = integral(s, e);
int si = 0, ei = N+1;
for(const CIR &o : CV) {
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(const TRI &o : TV) {
if(si < o.idx && o.idx < idx && !onTri(o, cp, s, e) && isIn(o, cp))
si = o.idx;
if(idx < o.idx && o.idx < ei && (onTri(o, cp, s, e) || 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(i, t.p[0], t.p[1]);
LV.eb(i, t.p[1], t.p[2]);
LV.eb(i, t.p[2], t.p[0]);
} else {
CV.eb();
CV.back().idx = i;
CV.back().input();
}
}
solveCir();
solveLine();
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
| ~~~~~~~~~~~^~~~~~~~~~~~~
paper.cpp: In function 'bool onTri(const TRI&, const pdd&, const pdd&, const pdd&)':
paper.cpp:95:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
95 | return isBet(a.p[0], p, a.p[1]) && isZero(ccw(a.p[0], a.p[1], p)) && isSameDir(a.p[0], s, e, a.p[1])
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paper.cpp:97:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
97 | || isBet(a.p[2], p, a.p[0]) && isZero(ccw(a.p[2], a.p[0], p)) && isSameDir(a.p[2], s, e, a.p[0]);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
1256 KB |
Output is correct |
| 2 |
Correct |
128 ms |
1248 KB |
Output is correct |
| 3 |
Correct |
137 ms |
1276 KB |
Output is correct |
| 4 |
Correct |
121 ms |
1244 KB |
Output is correct |
| 5 |
Correct |
123 ms |
1260 KB |
Output is correct |
| 6 |
Correct |
127 ms |
1252 KB |
Output is correct |
| 7 |
Correct |
144 ms |
1348 KB |
Output is correct |
| 8 |
Correct |
118 ms |
1256 KB |
Output is correct |
| 9 |
Correct |
105 ms |
1260 KB |
Output is correct |
| 10 |
Correct |
133 ms |
1244 KB |
Output is correct |
| 11 |
Correct |
43 ms |
1252 KB |
Output is correct |
| 12 |
Correct |
62 ms |
1248 KB |
Output is correct |
| 13 |
Correct |
92 ms |
1252 KB |
Output is correct |
| 14 |
Correct |
89 ms |
1348 KB |
Output is correct |
| 15 |
Correct |
92 ms |
1248 KB |
Output is correct |
| 16 |
Correct |
76 ms |
1252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
1352 KB |
Output is correct |
| 2 |
Correct |
191 ms |
1308 KB |
Output is correct |
| 3 |
Correct |
179 ms |
1408 KB |
Output is correct |
| 4 |
Correct |
189 ms |
1348 KB |
Output is correct |
| 5 |
Correct |
178 ms |
1348 KB |
Output is correct |
| 6 |
Correct |
865 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
154 ms |
1348 KB |
Output is correct |
| 8 |
Correct |
244 ms |
1328 KB |
Output is correct |
| 9 |
Correct |
191 ms |
1348 KB |
Output is correct |
| 10 |
Correct |
189 ms |
1308 KB |
Output is correct |
| 11 |
Correct |
386 ms |
1476 KB |
Output is correct |
| 12 |
Correct |
445 ms |
1368 KB |
Output is correct |
| 13 |
Correct |
78 ms |
1484 KB |
Output is correct |
| 14 |
Correct |
60 ms |
1380 KB |
Output is correct |
| 15 |
Correct |
88 ms |
1280 KB |
Output is correct |
| 16 |
Correct |
162 ms |
1396 KB |
Output is correct |
| 17 |
Correct |
152 ms |
1316 KB |
Output is correct |
| 18 |
Correct |
153 ms |
1352 KB |
Output is correct |
| 19 |
Correct |
145 ms |
1436 KB |
Output is correct |
| 20 |
Correct |
140 ms |
1368 KB |
Output is correct |
