链接：
http://o.boj.me/onlinejudge/showproblem.php?problem_id=1790这是我们那年（10年）校赛网络预赛的一道不是很难的题。可是事后我做了一个星期也还是WAWATLETLE。。。
现在想来当年还是太naive了，用了一些乱七八糟甚至不是算法的算法外加了一大堆补丁妄图水过此题。但是事实证明歪门邪道不会带来AC。
经历了那么多以后，虽然我还是蒟蒻，但是好歹掌握了多一点的东西了，于是这题隐约可捉了。
题目大意：
一条线段，N个圆，问这条线段上没被圆覆盖的部分的长度是多少。
做法：
弧扫描。
求出这N个圆与线段所在直线的两个交点（如果有），定一个序，低优先级的为入点，标0，高的为出点，标1；把线段的两个端点标为其他标记，比如2。然后将这最多2*N+2个点排序，按序扫描一遍。
当遇到第一次2且没有遇到第二次2的时候进行统计，初始化in=0，out=0，遇0，in++；遇1，out++；当in==out的时候，加上该点到下一点的距离，而这个就是距离就是未被覆盖的长度的一部分。归纳可知，正确性显然。此即为弧扫描的最简单应用。类似思想出现在poj1981，定长半径圆覆盖最多点问题。
直线方程竟然解错了导致wa了一次，太二了。
x + b * y + c = 0 => b = -(x1-x2)/(y1-y2)!!!!!
犯了错误，我们才会思考；找到不足，我们才能进步。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define sqr(x) ((x) * (x))
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
#define maxn 1005
int comp(double x)
{
return fabs(x) < eps?0:x <-eps?-1:1;
}
struct point
{
double x,y;
point(){}
point(double a,double b):x(a),y(b){}
point operator -(point p)
{
return point(x - p.x,y - p.y);
}
double norm()
{
return sqrt(sqr(x) + sqr(y));
}
};
struct circle
{
point c;
double r;
circle(){}
circle(point _c,double _r):c(_c),r(_r){}
}c[maxn];
struct line
{
point p,q;
double a,b,c;
line(){}
line(point _p,point _q):p(_p),q(_q)
{
if(comp(p.x - q.x) == 0)
{
a = 1.0;
b = 0.0;
c = -p.x;
}
else if(comp(p.y - q.y) == 0)
{
a = 0.0;
b = 1.0;
c = -p.y;
}
else
{
a = 1.0;
b = -(p.x - q.x) / (p.y - q.y);
c = -(b * p.y + p.x);
}
}
}L;
struct sol
{
point p;
int flag;
sol(){}
sol(point _p,int _f):p(_p),flag(_f){}
}s[maxn * 2];
bool operator <(const point a,const point b)
{
return comp(a.x - b.x) < 0 || (comp(a.x - b.x) == 0 && comp(a.y - b.y) < 0);
}
bool operator <(const sol &a,const sol &b)
{
return a.p < b.p;
}
int n;
void calc(circle o,point &p,point &q)
{
double A,B,C,det;
if(comp(L.a) == 0)
{
A = sqr(L.a) + sqr(L.b);
B = 2.0 * L.a * (L.c + L.b * o.c.y) - 2.0 * sqr(L.b) * o.c.x;
C = sqr(L.c + L.b * o.c.y) + sqr(L.b) * (sqr(o.c.x) - sqr(o.r));
det = sqr(B) - 4.0 * A * C;
if(comp(det) < 0)
p = q = L.p;
else
{
if(comp(det) == 0)
det = 0.0;
p.x = (-B + sqrt(det))/(2.0 * A);
q.x = (-B - sqrt(det))/(2.0 * A);
p.y = -(L.a * p.x + L.c) / L.b;
q.y = -(L.a * q.x + L.c) / L.b;
if(q < p)
swap(p,q);
}
}
else
{
A = sqr(L.a) + sqr(L.b);
B = 2.0 * (L.b * L.c + L.a * L.b * o.c.x - sqr(L.a) * o.c.y);
C = sqr(L.c + L.a * o.c.x) + sqr(L.a) * (sqr(o.c.y) - sqr(o.r));
det = sqr(B) - 4.0 * A * C;
if(comp(det) < 0)
p = q = L.p;
else
{
if(comp(det) == 0)
det = 0.0;
p.y = (-B + sqrt(det)) / (2.0 * A);
q.y = (-B - sqrt(det)) / (2.0 * A);
p.x = -(L.b * p.y + L.c) / L.a;
q.x = -(L.b * q.y + L.c) / L.a;
if(q < p)
swap(p,q);
}
}
}
int main()
{
while(scanf("%d",&n) == 1 && n)
{
for(int i = 0;i < n;i++)
{
double x,y,r;
scanf("%lf %lf %lf",&x,&y,&r);
c[i] = circle(point(x,y),r);
}
double x1,x2,y1,y2;
scanf("%lf %lf",&x1,&y1);
scanf("%lf %lf",&x2,&y2);
L = line(point(x1,y1),point(x2,y2));
int cnt = 0;
s[cnt++] = sol(point(x1,y1),2);
s[cnt++] = sol(point(x2,y2),2);
for(int i = 0;i < n;i++)
{
point p,q;
calc(c[i],p,q);
s[cnt++] = sol(p,0);
s[cnt++] = sol(q,1);
}
sort(s,s + cnt);
int mark = 0,in = 0,out = 0;
double ans = 0.0;
for(int i = 0;i < cnt - 1;i++)
{
switch(s[i].flag)
{
case 0:
in++;
break;
case 1:
out++;
break;
case 2:
mark++;
break;
}
if(mark == 1 && in == out)
ans += (s[i].p - s[i+1].p).norm();
}
printf("%.4lf\n",ans);
}
}
å
forward word