Submission #796747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796747	2023-07-28T16:49:44 Z	junk727	Lonely mdic (kriii1_L)	C++17	0 / 1	220 ms	308 KB

L

#include <bits/stdc++.h>
#define fastio cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
 
typedef long double ld;
typedef pair<ld,ld> pd;
#define all(x) (x).begin(),(x).end()
 
const ld PI = acos(-1);
const ld EPS = 1e-10;
inline bool is_zero(ld x){return -EPS<=x && x<=EPS;} 
 
struct point
{
    point() {}
    point(ld x, ld y) : x(x),y(y) {}
 
    ld 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};}
    ld len() {return x*x+y*y;}
    ld angle() {return atan2(y,x);}
 
    bool operator == (const point &p) const { return x==p.x && y==p.y;}
};
 
struct circle
{
    circle() {}
    circle(point c, int r) : c(c), r(r) {}
 
    point c;
    int r;
 
    ld green(ld s, ld e)
    {
        ld a = r*r*(e-s);
        ld b = c.x * r * (sin(e)-sin(s));
        ld d = c.y * r * (cos(s)-cos(e));
        return (a+b+d)/2;
    }
 
    bool operator == (const circle &m) const {return c==m.c && r==m.r;}
};
 
ld mod(ld x)
{
    while(x<0) x+=2*PI;
    while(x>=2*PI) x-=2*PI;
    return x;
}
 
int main()
{
    int n,ans=0; cin >> n;
 
    vector<circle> vc(n);
 
    for(int i=0;i<n;i++)
    {
        int x,y,r; cin >> x >> y >> r;
        vc[i] = {{(ld)x,(ld)y},r};
        for(int j=0;j<i;j++)
        {
            if(vc[i]==vc[j])
            {
                i--; n--; ans++;
                break;
            }
        }
    }
 
    vector<bool> in(n,0);
    vector<ld> area(n,0);
 
    sort(vc.begin(),vc.begin()+n,[](circle &p, circle &q){return p.r>q.r;});
 
    for(int x=0;x<n;x++)
    {
        in.clear(); ld temp=0;
        for(int i=0;i<n;i++)
        {
            if(in[i] || i==x) continue;
 
            vector<pd> vx = {};
 
            for(int j=0;j<n;j++)
            {
                point pt = vc[j].c-vc[i].c; ld d = pt.len();
                if(j==x || i==j || in[j] || d>=(vc[i].r+vc[j].r)*(vc[i].r+vc[j].r)) continue;
                if(d <= (vc[i].r-vc[j].r)*(vc[i].r-vc[j].r)) {in[j]=1; continue;}
 
                ld z = pt.angle(), dt = acos((vc[i].r*vc[i].r+d-vc[j].r*vc[j].r)/(2*vc[i].r*sqrt(d)));
                ld l = mod(z-dt), r = mod(z+dt);
 
                if(l>r) vx.push_back({0,r}), vx.push_back({l,2*PI});
                else vx.push_back({l,r});
            }
 
            if(vx.empty()) {temp+=vc[i].r*vc[i].r*PI; continue;}
            sort(all(vx));
 
            vx.push_back({2*PI,2*PI});
 
            ld r=0;
            for(pd j : vx)
            {
                if(r<j.first) temp += vc[i].green(r,j.first), r=j.second; 
                else r=max(r,j.second);
            }
        }
        area[x]=temp;
    }
 
    in.clear(); ld comp=0;
    for(int i=0;i<n;i++)
    {
        if(in[i]) continue;
 
        vector<pd> vx = {};
 
        for(int j=0;j<n;j++)
        {
            point pt = vc[j].c-vc[i].c; ld d = pt.len();
            if(i==j || in[j] || d>=(vc[i].r+vc[j].r)*(vc[i].r+vc[j].r)) continue;
            if(d <= (vc[i].r-vc[j].r)*(vc[i].r-vc[j].r)) {in[j]=1; continue;}
 
            ld z = pt.angle(), dt = acos((vc[i].r*vc[i].r+d-vc[j].r*vc[j].r)/(2*vc[i].r*sqrt(d)));
            ld l = mod(z-dt), r = mod(z+dt);
            if(l>r) vx.push_back({0,r}), vx.push_back({l,2*PI});
            else vx.push_back({l,r});
        }
 
        if(vx.empty()) {comp+=vc[i].r*vc[i].r*PI; continue;}
        sort(all(vx));
 
        vx.push_back({2*PI,2*PI});
 
        ld r=0;
        for(pd j : vx)
        {
            if(r<j.first) comp += vc[i].green(r,j.first), r=j.second; 
            else r=max(r,j.second);
        }
    }
    
    for(int i=0;i<n;i++) if(is_zero(comp-area[i])) ans++;
    cout << ans;
}

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	212 KB	Output is correct
2	Correct	21 ms	296 KB	Output is correct
3	Correct	157 ms	296 KB	Output is correct
4	Correct	144 ms	308 KB	Output is correct
5	Incorrect	220 ms	212 KB	Output isn't correct
6	Halted	0 ms	0 KB	-