Submission #795326

#	Time	Username	Problem	Language	Result	Execution time	Memory
795326		junk727	Lonely mdic (kriii1_L)	C++17	0 / 1	23 ms	212 KiB

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-27;
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, int id) : c(c), r(r), id(id) {}

    point c;
    int r,id;

    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()
{
    fastio;
    int n,ans=0; cin >> n;

    vector<circle> vc(n);
    vector<bool> in(n,0);
    vector<ld> area(n,0);

    for(int i=0;i<n;i++)
    {
        int x,y,r; cin >> x >> y >> r;
        vc[i] = {{(ld)x,(ld)y},r,i};
        for(int j=0;j<i;j++)
        {
            if(vc[i]==vc[j])
            {
                i--; n--; ans++;
                break;
            }
        }
    }

    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