#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 = 505;
const llf eps = 1e-14L;
const llf pi = acos(-1);
int sgn(llf x){
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
llf norm(llf x){
x = fmod(x, 2 * pi);
while(x < 0) x += 2 * pi;
return x;
}
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 sgn(x - p.x) == 0 && sgn(y - p.y) == 0; }
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>;
llf fix(llf x){
if(sgn(x) == 0) return 0;
return x;
}
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);
}
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){
llf dist = (x - C).dist2();
if(sgn(dist - r * r) > 0) return 0;
return 1;
}
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 (sgn(a) == 0){ // if parallel
auto b1=s1.dot(v1), c1=e1.dot(v1),
b2=s2.dot(v1), c2=e2.dot(v1);
if (sgn(a1) || sgn(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 (sgn(a) < 0) { a = -a; a1 = -a1; a2 = -a2; }
if (0< sgn(a1) || a<-a1 || 0<sgn(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(sgn(delta.dist2()) == 0) 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(fix(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(fix(r * r - dis * dis));
X = M - D;
Y = M + D;
return 1;
}
llf dx[MAXN][MAXN];
llf ret;
bool sameDirection(punk A, punk B, punk C, punk D){
return sgn((B - A).dot(D - C)) > 0;
}
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++){
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;
}
}
}
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)){
bool over = false;
punk X, Y;
if(segmentIntersection(P, Q, j.p[0], j.p[1], X, Y) == 2 &&
sameDirection(A, B, j.p[0], j.p[1])) over = true;
if(segmentIntersection(P, Q, j.p[1], j.p[2], X, Y) == 2 &&
sameDirection(A, B, j.p[1], j.p[2])) over = true;
if(segmentIntersection(P, Q, j.p[2], j.p[0], X, Y) == 2 &&
sameDirection(A, B, j.p[2], j.p[0])) over = true;
if(over){
// puts("it's over");
if(j.idx < x.idx) min_idx = max(min_idx, j.idx);
}
else{
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) 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;
cin >> 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("");
}
}
Compilation message
paper.cpp: In function 'int main()':
paper.cpp:306:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
306 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
paper.cpp:313:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
313 | scanf("%d %d %d",&x,&y,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
1772 KB |
Output is correct |
| 2 |
Correct |
171 ms |
1772 KB |
Output is correct |
| 3 |
Correct |
160 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
145 ms |
1772 KB |
Output is correct |
| 5 |
Correct |
138 ms |
1824 KB |
Output is correct |
| 6 |
Correct |
167 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
149 ms |
1772 KB |
Output is correct |
| 8 |
Correct |
140 ms |
1772 KB |
Output is correct |
| 9 |
Correct |
120 ms |
1772 KB |
Output is correct |
| 10 |
Correct |
125 ms |
1772 KB |
Output is correct |
| 11 |
Correct |
54 ms |
1772 KB |
Output is correct |
| 12 |
Correct |
55 ms |
1724 KB |
Output is correct |
| 13 |
Correct |
106 ms |
1716 KB |
Output is correct |
| 14 |
Correct |
96 ms |
1792 KB |
Output is correct |
| 15 |
Correct |
103 ms |
1772 KB |
Output is correct |
| 16 |
Correct |
69 ms |
1772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
476 ms |
1824 KB |
Output is correct |
| 2 |
Correct |
517 ms |
2004 KB |
Output is correct |
| 3 |
Correct |
454 ms |
1900 KB |
Output is correct |
| 4 |
Correct |
519 ms |
2028 KB |
Output is correct |
| 5 |
Correct |
473 ms |
1824 KB |
Output is correct |
| 6 |
Correct |
967 ms |
1900 KB |
Output is correct |
| 7 |
Correct |
293 ms |
2084 KB |
Output is correct |
| 8 |
Correct |
752 ms |
2016 KB |
Output is correct |
| 9 |
Correct |
500 ms |
2028 KB |
Output is correct |
| 10 |
Correct |
530 ms |
1900 KB |
Output is correct |
| 11 |
Correct |
247 ms |
1900 KB |
Output is correct |
| 12 |
Correct |
284 ms |
1900 KB |
Output is correct |
| 13 |
Correct |
67 ms |
2028 KB |
Output is correct |
| 14 |
Correct |
58 ms |
1932 KB |
Output is correct |
| 15 |
Correct |
170 ms |
1772 KB |
Output is correct |
| 16 |
Correct |
438 ms |
2028 KB |
Output is correct |
| 17 |
Correct |
422 ms |
1872 KB |
Output is correct |
| 18 |
Correct |
450 ms |
2028 KB |
Output is correct |
| 19 |
Correct |
430 ms |
2028 KB |
Output is correct |
| 20 |
Correct |
311 ms |
1900 KB |
Output is correct |
