记录编号	363806	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]下落的圆盘	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2017-01-13 15:32:29	内存使用	0.33 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const double PI = acos(-1);
struct point
{
    double x, y;
    point(){}
    point(double _x, double _y):x(_x), y(_y){}
    inline double angle()
    {
        return atan2(y, x);
    }
    inline double dist(point &o)
    {
        return sqrt((x-o.x)*(x-o.x)+(y-o.y)*(y-o.y));
    }
    point operator-(point &o)
    {
        return point(x-o.x, y-o.y);
    }
};
struct circle
{
    point o;
    double r;
    circle(){}
}cs[1001];
struct range
{
    double l, r;
    range(){}
    range(double _l, double _r):l(_l), r(_r){}
    bool operator<(const range &o)const
    {
        return l < o.l || (l == o.l && r < o.r);
    }
};vector<range> rs;
double eps = 1e-16;
inline int dcmp(double x)
{
    if(x < -eps)return -1;
    else if(x > eps)return 1;
    else return 0;
}
inline int dcmp(double x, double y)
{
    return dcmp(x-y);
}
void get_insection(circle &a, circle &b, double d)
{
    double alpha = (b.o-a.o).angle()+PI;
    double det = acos((a.r*a.r+d*d-b.r*b.r)/(2*a.r*d));
    double newL = alpha-det, newR = alpha+det;
    if(newL >= 0 && newR <= 2*PI)
        rs.push_back(range(newL, newR));
    else if(newL < 0)
    {
        rs.push_back(range(newL+2*PI, 2*PI));
        rs.push_back(range(0, newR));
    }else
    {
        rs.push_back(range(newL, 2*PI));
        rs.push_back(range(0, newR-2*PI));
    }
}
double insection_unit()
{
    double s = 0;
    sort(rs.begin(), rs.end());
    double st = 0.0, ed = 0.0;
    for(int i = 0; i < rs.size(); i++)
    {
        if(rs[i].l > ed)
        {
            s += ed-st;
            st = rs[i].l, ed = rs[i].r;
        }else
            ed = max(ed, rs[i].r);
    }
    s += ed-st;
    return 2*PI-s;
}
int main()
{
    freopen("disc.in", "r", stdin);
    freopen("disc.out", "w", stdout);
    double ans = 0.0;
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lf %lf %lf", &cs[i].r, &cs[i].o.x, &cs[i].o.y);
    for(int i = 1; i <= n; i++)
    {
        bool flag = true;
        rs.clear();
        for(int j = i+1; j <= n; j++)
        {
            double d = cs[i].o.dist(cs[j].o);
            if(cs[j].r-cs[i].r > d) //完全被遮挡，不再管了
            {
                flag = false;
                break;
            }
            //两圆相交
           // if(dcmp(cs[i].r+cs[j].r, d) > 0 && dcmp(fabs(cs[i].r-cs[i].r), d) < 0)
            if(cs[i].r+cs[j].r > d && fabs(cs[i].r-cs[j].r) < d)
               get_insection(cs[i], cs[j], d); //计算b覆盖掉a的部分
        }
        if(flag) 
                    //覆盖区间合并
            ans += insection_unit()*cs[i].r; //如果最后能够看到cs[i],计算看到部分的弧长
    }
    printf("%.3lf\n", ans);
    return 0;
}