考虑如下的问题：
往数轴上丢若干线段，问最后线段覆盖数轴长度
上面这一题显然是离散化，能在\(O(n)\)的时间内出解，唔，线段树是吧，那货是\(O(n\log n)\)的，不考虑，不考虑~
然后考虑下面一题：
往平面直角坐标系\(xOy\)内丢若干矩形，问现在从\(z=INF\)的地方往下看，看到的矩形边界长度为多少
显然，后面丢下去的若干矩形会覆盖前面的矩形，从而使矩形能被看到的边界变小，我们只用枚举矩形即可，最后矩形会变成若干线段，求出这些线段的总长度即可
那么这题不是一样的么？考虑圆\(O_i\)，那么它可被\(O_{i+1}\dots O_n\)覆盖，我们可以求出被覆盖的弧的起始角和终止角，便能求出弧长
所有的圆剩下的弧长和就是答案
如图，我们可以很容易地求出\(\alpha\)角和\(\beta\)角，不需要求交点！！！
然后注意两角跨越坐标轴时的情况即可
AC-Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
using namespace std;
const double EPS=1e-8,INF=1e200,PI=3.1415926535898;
const int MAXN=1005;
typedef pair<double,double> DD;
typedef vector< DD >::iterator Vit;
int n;
double R[MAXN],A[MAXN],B[MAXN],ans,dist;
double alpha,beta,ang,lef,rig;
vector< DD >seg;
DD ptmp;
bool cover;
double Sqr(double x)
{
return x*x;
}
double Dist(double x1,double y1,double x2,double y2)
{
return sqrt(Sqr(x1-x2)+Sqr(y1-y2));
}
double angle(double A,double B,double C)
{
return acos((Sqr(A)+Sqr(B)-Sqr(C))/(2*A*B));//余弦定理
}
int Sign(double x)
{
if (x>EPS)
return 1;
return (0-(x<(-EPS)));
}
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%lf%lf%lf",&R[i],&A[i],&B[i]);
for (int i=0;i<n;i++)
{
seg.clear();
cover=false;
for (int j=i+1;j<n;j++)
{
dist=Dist(A[i],B[i],A[j],B[j]);
//完全覆盖了
if (Sign(R[j]-R[i])>=0&&Sign(dist-(R[j]-R[i]))<=0)
{
cover=true;
break;
}
//这个圆j在圆i的里面
if (Sign(dist-(R[j]+R[i]))>=0||Sign(dist-abs(R[j]-R[i]))<=0)
continue;
alpha=atan2(B[j]-B[i],A[j]-A[i]);
beta=angle(R[i],dist,R[j]);
ptmp=make_pair(alpha-beta,alpha+beta);
if (Sign(ptmp.first)<=0&&Sign(ptmp.second)<=0)
seg.push_back(make_pair(2*PI+ptmp.first,2*PI+ptmp.second));
else if (Sign(ptmp.first<0))
{
seg.push_back(make_pair(2*PI+ptmp.first,2*PI));
seg.push_back(make_pair(0,ptmp.second));
}
else
seg.push_back(ptmp);
}
if (cover)
continue;
seg.push_back(make_pair((double)10.0,(double)10.0));
sort(seg.begin(),seg.end());
ang=lef=rig=0;
for (Vit it=seg.begin();it!=seg.end();it++)
{
if (Sign(rig-it->first)>=0)
rig=max(rig,it->second);
else
{
ang+=rig-lef;
lef=it->first;
rig=it->second;
}
}
ans+=R[i]*(2*PI-ang);
}
printf("%.3lf\n",ans);
}
/*
* 计算几何毁一生
*/