Submission #793366

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
793366	2023-07-25T18:29:24 Z	junk727	Lonely mdic (kriii1_L)	C++17	0 / 1	1 ms	212 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-14;
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);}
};

struct circle
{
    circle() {}
    circle(point c, int r, int id) : c(c), r(r), id(id) {}

    point c;
    int r,id;
};


int 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 0; 
    if(d < (c1.r-c2.r)*(c1.r-c2.r) - EPS) return 0;

    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;
    if(is_zero(dt)) return tp;
    ld v1 = mod(ct-dt);
    mp[tp++] = v1;
    v1 = mod(ct+dt);
    mp[tp++] = v1;
    return tp;
}

int sq(int x){return x*x;}

int main()
{
    int n; cin >> n;

    int ans = 0;

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

    for(int i=0;i<n;++i)
    {
        int x,y,r; cin >> x >> y >> r;
        vc.push_back({{(ld)x,(ld)y},r,i});
    }

    sort(all(vc),[](circle &p, circle &q){return p.r>q.r;});

    for(int i=0;i<n;i++)
    {
        if(in[i]){ans++; 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>=sq(vc[i].r+vc[j].r)) continue;
            if(d <= sq(vc[i].r-vc[j].r)) {in[j]=1; continue;}

            ld mp[2];
            int tp = meetcc(vc[i],vc[j],mp);
            if(tp) 
            {
                if(mp[0]>mp[1]) vx.push_back({mp[0],2*PI}), vx.push_back({0,mp[1]});
                else vx.push_back({mp[0],mp[1]});
            }
        }

        sort(all(vx));

        if(vx.empty()) continue;
        vx.push_back({2*PI,2*PI});

        ld r=0,chk=1;
        for(pd j : vx)
        {
            if(r<j.first) chk=0, r=j.second;
            else r=max(r,j.second);
        }

        if(chk) ans++;
    }

    cout << ans;
}

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-