UVa1308 LA2572

目前为止，这个题处理精度的方法很值得学习。。

按照从里往外的顺序找圆与其他圆的所有交点的极角，根据这些交点的极角求小圆弧的中点的极角，再根据极角求坐标。

对于每个小圆弧中点，从外往里找，第一个满足 “点在圆外面” 的圆，一定是可见的。

这个方法对于多边形的也适用，可以在桌子上面放几本大小不同的书，想一想 - -

int topmost ( Point p ) {
    for ( int i = n-1; i >= 0; --i ) if ( Length(circle[i].c-p) < circle[i].r ) return i;
    return -1;
}

关于精度的处理，是这样的：

对于每个圆的半径r，分别计算r+eps，与r-eps时的小圆弧中点坐标，然后进行判断；

为了避免对  “没有交点的圆”  的特殊判断，采用加入 0 和 2*PI 这两个极角处理。

那么每个小圆弧中点的极角为

double mid = (rad[j]+rad[j+1])/2.0;

主要代码：

        for ( i = 0; i < n; ++i ) {
            vector < double > rad; rad.push_back(0); rad.push_back(PI*2);
            for ( j = 0; j < n; ++j ) getCircleCircleIntersection(circle[i],circle[j], rad);
            sort ( rad.begin(), rad.end() );
            for ( j = 0; j < rad.size(); ++j ) {
                double mid = (rad[j]+rad[j+1])/2.0;
                for ( int side = -1; side <= 1; side += 2 ) {
                    double r2 = circle[i].r - side*eps;
                    int t = topmost(Point(circle[i].c.x + cos(mid)*r2, circle[i].c.y + sin(mid)*r2));
                    if ( t >= 0 ) visible[t] = true;
                }
            }
        }