| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 376451 |
2021-03-11T13:38:34 Z |
gs14004 |
색종이 (kriii3_T) |
C++17 |
|
268 ms |
1612 KB |
#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 = 205;
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 tie(x,y)==tie(p.x,p.y); }
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); }
T 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; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double 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(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
};
using punk = Point<llf>;
const llf eps = 1e-9;
const llf pi = acos(-1);
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);
}
int sgn(llf x){
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
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){
return (C - x).dist2() <= r * r + eps;
}
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 (a == 0) { //if parallel
auto b1=s1.dot(v1), c1=e1.dot(v1),
b2=s2.dot(v1), c2=e2.dot(v1);
if (a1 || 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 (a < 0) { a = -a; a1 = -a1; a2 = -a2; }
if (0<a1 || a<-a1 || 0<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(delta.dist2() < eps) return false;
double r = r1 + r2, d2 = delta.dist2();
double p = (d2 + r1*r1 - r2*r2) / (2.0 * d2);
double h2 = r1*r1 - p*p*d2;
if (d2 > r*r || h2 < 0) return false;
P mid = a + delta*p, per = delta.perp() * sqrt(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(r * r - dis * dis);
X = M - D;
Y = M + D;
return 1;
}
llf dx[MAXN][MAXN];
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;
assert(fabs(C.dist2() - x.r * x.r) < eps);
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++){
if(fabs(witness[i] - witness[i - 1]) < eps) continue;
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) - x.C.cross(p1));
// printf("%d %d %d %.10Lf\n", min_idx + 1, x.idx, max_idx - 1, result);
dx[min_idx + 1][x.idx] += result;
dx[min_idx + 1][max_idx] -= result;
dx[x.idx + 1][x.idx] -= result;
dx[x.idx + 1][max_idx] += 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 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)){
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]);
dx[min_idx + 1][x.idx] += result;
dx[min_idx + 1][max_idx] -= result;
dx[x.idx + 1][x.idx] -= result;
dx[x.idx + 1][max_idx] += result;
}
}
}
int main(){
int n; scanf("%d",&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 <= n; j++){
if(i) dx[i][j] += dx[i-1][j];
if(j) dx[i][j] += dx[i][j-1];
if(i&&j) dx[i][j] -= dx[i-1][j-1];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
printf("%.20Lf ", 0.5 * (dx[j][i] - dx[j + 1][i]));
}
puts("");
}
}
Compilation message
paper.cpp: In function 'int main()':
paper.cpp:268:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
268 | int n; scanf("%d",&n);
| ~~~~~^~~~~~~~~
paper.cpp:273:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
273 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
paper.cpp:280:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
280 | scanf("%d %d %d",&x,&y,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
1516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
268 ms |
1612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
