답안 #796335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796335	2023-07-28T09:54:47 Z	junk727	Lonely mdic (kriii1_L)	C++17	0 / 1	65 ms	320 KB

L

#include <bits/stdc++.h>
#define fastio cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;

typedef 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 circle
{
    circle() {}
    circle(int x, int y, int r) : x(x), y(y), r(r) {}

    int x,y,r;

    ld green(ld s, ld e)
    {
        ld a = r*r*(e-s);
        ld b = x * r * (sin(e)-sin(s));
        ld d = y * r * (cos(s)-cos(e));
        return (a+b+d)/2;
    }

    ld dist(const circle &m)
    {
        return (m.x-x)*(m.x-x) + (m.y-y)*(m.y-y);
    }

    ld angle(const circle &m)
    {
        return atan2((m.y-y),(m.x-x));
    }

    bool operator == (const circle &m) const {return x==m.x && y==m.y && r==m.r;}
};

void meetcc(circle c1, circle c2, ld mp[])
{
    ld d = c1.dist(c2);
    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 = c1.angle(c2);
 
    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] = {x,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++)
            {
                ld d = vc[i].dist(vc[j]);
                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++)
        {
            ld d = vc[i].dist(vc[j]);   
            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;
}

Subtask #1

0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	212 KB	Output is correct
2	Correct	6 ms	212 KB	Output is correct
3	Correct	65 ms	320 KB	Output is correct
4	Correct	53 ms	316 KB	Output is correct
5	Incorrect	65 ms	212 KB	Output isn't correct
6	Halted	0 ms	0 KB	-