Submission #796261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796261	2023-07-28T08:33:34 Z	junk727	Lonely mdic (kriii1_L)	C++17	0 / 1	215 ms	340 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;}
};

void meetcc(circle c1, circle c2, ld mp[])
{
    ld d = (c2.c-c1.c).len();
    if(d > (c1.r+c2.r)*(c1.r+c2.r) + EPS) return; 
    if(d < (c1.r-c2.r)*(c1.r-c2.r) - EPS) return;
 
    ld ct = (c2.c-c1.c).angle();
 
    ld temp = (c1.r*c1.r + d - c2.r*c2.r) / (2*c1.r*sqrt(d));
    if(temp<-1) temp=-1;
    if(temp>1) temp=1;
    
    auto mod = [&](ld x)
    {
        while(x<0) x+=2*PI;
        while(x>=2*PI) x-=2*PI;
        return x;
    };
 
    ld dt = acos(temp);
     
    int tp=0;
    ld v1 = mod(ct-dt);
    mp[tp++] = v1;
    v1 = mod(ct+dt);
    mp[tp++] = v1;
    return;
}

int main()
{
    fastio;
    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;});

    auto mod = [&](ld x)
    {
        while(x<0) x+=2*PI;
        while(x>=2*PI) x-=2*PI;
        return x;
    };

    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});
                */
                ld mp[2]; meetcc(vc[i],vc[j],mp);
                ld l = mp[0], r = mp[1];

                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});
            */

            ld mp[2]; meetcc(vc[i],vc[j],mp);
            ld l = mp[0], r = mp[1];

            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;
}

Compilation message

L.cpp: In function 'int main()':
L.cpp:102:10: warning: variable 'mod' set but not used [-Wunused-but-set-variable]
  102 |     auto mod = [&](ld x)
      |          ^~~

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	212 KB	Output is correct
2	Correct	21 ms	212 KB	Output is correct
3	Correct	167 ms	340 KB	Output is correct
4	Correct	152 ms	332 KB	Output is correct
5	Incorrect	215 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-