【BZOJ1043】[HAOI2008] 下落的圆盘

　　smg啊这种水题调了3h……前途一片灰暗……
　　对于每个圆，它能够把前面的圆覆盖，同时会被后面的圆覆盖，它所贡献的周长是它自身周长减去被覆盖的部分，而被覆盖的部分是可以算出来的，用当前圆暴力和后面的圆全部求个交。对于一个圆，它被另外一个圆给交了，其被覆盖的圆弧的圆心角是确定的。也就是说，这个圆被覆盖的总弧度可以用各个圆心角的并得到。每被覆盖一次，就可以得到一个被覆盖的弧度的区间。在平面直角坐标系上这个区间是 [−π,π] 的，可以把它加上 pi ，这样会好处理些。
　　那么就把问题转化成了一些弧度区间的并。这个另开一篇文章讲好了。
　　求并的时间是 O(nlogn) 的，故总时间是 O(n2logn) 的。
　　一开始把GetAng的返回值写成了bool
　　要注意圆覆盖的情况和同心圆的情况。这样用余弦定理算圆心角的时候会爆NaN。
　　woc用一个错误的标程对着调了几h
　　另外这个blog下的程序似乎是有错误的，可以被卡掉。
　　http://blog.csdn.net/jiangyuze831/article/details/40580789

my code：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,_=b;i<=_;i++)
#define per(i,a,b) for(int i=a,_=b;i>=_;i--)
#define pii pair<double , double>
#define mp make_pair
#define maxn 1007

inline int rd() {
    char c = getchar();
    while (!isdigit(c)) c = getchar() ; int x = c - '0';
    while (isdigit(c = getchar())) x = x * 10 + c - '0';
    return x;
}

const double pi = acos(-1.0);
const double eps = 0;

typedef vector<pii>::iterator iter_pii;

template<class T> inline void upmax(T&a , T b) { if (a < b) a = b ; }

template<class T> inline T sqr(T x) { return x * x ; }

inline int fcmp(double a , double b) {
    if (fabs(a - b) <= eps) return 0;
    if (a < b - eps) return -1;
    return 1;
}

struct Point {
    double x , y;
    Point() { x = y = 0 ; }
    Point(double x , double y):x(x) , y(y) {  }
    inline double GetAng() { return atan2(y , x); }
};

Point operator-(Point a , Point b) { return Point(a.x - b.x , a.y - b.y) ; }

inline double GetPointDis(Point a , Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)) ; }

struct Circle {
    Point o;
    double r;
    Circle() {}
    Circle(double r , Point o):r(r) , o(o) { }
}circle[maxn];

int n;

vector<pii> tmp;

void input() {
    n = rd();
    rep (i , 1 , n) {
        double r , x , y;
        scanf("%lf%lf%lf" , &r , &x , &y);
        circle[i] = Circle(r , Point(x , y));
    }
}

void CircleIntersect(Circle&a , Circle&b) {
    double dis = GetPointDis(a.o , b.o);
    if (fcmp(dis , a.r + b.r) > 0 || fcmp(dis , a.r - b.r) < 0) return;
    if (fcmp(dis , b.r - a.r) <= 0 || (dis == 0 && a.r == b.r)) {
        tmp.push_back(mp(0 , pi + pi));
        return;
    }

    //assert(a.r != 0);
    //assert(dis != 0);

    double theta = (b.o - a.o).GetAng() + pi , 
           delta = acos((sqr(a.r) + sqr(dis) - sqr(b.r)) / (2.0 * a.r * dis));

    if (theta < delta) {
        tmp.push_back(mp(0 , theta + delta));
        tmp.push_back(mp(theta - delta + pi + pi , pi + pi));
    }
    else if (theta + delta > pi + pi) {
        tmp.push_back(mp(theta - delta , pi + pi));
        tmp.push_back(mp(0 , theta + delta - pi - pi));
    }
    else {
        tmp.push_back(mp(theta - delta , theta + delta));
    }
}

double calc(int i) {
    tmp.clear();
    rep (j , i + 1 , n)
        CircleIntersect(circle[i] , circle[j]);
    sort(tmp.begin() , tmp.end());

    double res = 0.0 , st = 0.0 , ed = 0.0;
    for (iter_pii it = tmp.begin() ; it != tmp.end() ; it ++)
        if (fcmp(it -> first , ed) > 0)
            res += ed - st , st = it -> first , ed = it -> second;
        else
            ed = max(ed , it -> second);
    res += ed - st;
    return (pi + pi - res) * circle[i].r;
}

void solve() {
    double ans = 0;
    per (i , n , 1)
        ans += calc(i);
    printf("%.3lf\n" , ans);
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("data.txt" , "r" , stdin);
        freopen("data.out" , "w" , stdout);
    #endif
    input();
    solve();
    return 0;
}