Viva Confetti UVALive - 2572

**离散化的思想，将每一个圆都分成一个个小圆弧


const int maxn = 100+10;
Point center[maxn];
double radius[maxn];
int n;
bool vis[maxn];
int judge(Point p)
{
    for(int i = n-1; i >= 0; --i)
        if(Length(p-center[i])<radius[i])
            return i;
    return -1;
}
void CCI(Point c1,double r1,Point c2,double r2,vector<double> &v)
{
    double d = Length(c1-c2);
    if(dcmp(d)==0)
        return;
    if(dcmp(r1 + r2 - d) < 0)
        return ;
    if(dcmp(fabs(r1-r2)-d) > 0)
        return ;

    double rad = angle(c2-c1);
    double da = acos((r1*r1+d*d-r2*r2)/2*r1*d);

    v.push_back(rad + da);
    v.push_back(rad - da);
}
int main(void)
{
    while(cin>>n&&n)
    {
        me(vis);
        for(int i = 0; i < n; ++i) //输入
            cin>>center[i].x>>center[i].y>>radius[i];

        for(int i = 0; i < n; ++i)
        {
            vector<double> rad;
            rad.push_back(0);
            rad.push_back(2*pi);
            for(int j = 0; j < n; ++j)
                CCI(center[i],radius[i],center[j],radius[j],rad);
            sort(rad.begin(),rad.end());
            for(int j = 0; j < rad.size()-1; ++j)
            {
                double mid = (rad[j]+rad[j+1])/2.0;
                for(int k = - 1; k <= 1; k += 2)
                {
                    double rr = radius[i] + k * eps;
                    int t = judge(Point(center[i].x+ rr*cos(mid),center[i].y+rr*sin(mid)));
                    if(t != -1)
                        vis[t] = true;
                }
            }
        }
        int num = 0;
        for(int i = 0; i < n; ++i)
            if(vis[i])
                num++;
        cout<<num<<endl;
    }

    return 0;
}