[HDOJ3425 Coverage]【求圆与线段覆盖部分的一个沙茶方法。。。】

【题目大意】
给定一个线段，和n个圆。
如果线段上某点被某一个圆覆盖，那么就算被覆盖。
最终问被覆盖点占线段总长的百分比。
【算法分析】
圆与线段交点有很多很快的方法，但是我介绍一种异常沙茶，巨慢，却不大容易错的方法。（实际上就是不用分类什么的而已。。。）
首先，对线段两点建立一个向量，然后就可以利用向量伸缩来很方便的表示该线段。
对于一个线段和一个圆。我们先用点到圆心距离为函数。由于他的单峰性质，二分得那个离圆最近的点。
（好像人们都比较喜欢三分，在此表示不解）
现在我们得到了圆覆盖掉的线段上的一个点。
于是我们现在就可以在这个点的基础上，向线段的两个端点爬山。
（就是设一个步长，如果爬出去就停止，并不停将步长除以2）
然后爬完了。得到那两个边缘点就是圆覆盖了线段的两个边缘点。
整个算法复杂度O(lg K) K为坐标距离除以eps。
【一些小技巧】
设向量为(x1,y1) -> (x2,y2)
那么我们就可以用一个数rate表示线段上的点。（其中0<=rate<=1）
具体就是( x1+rate*(x2-x1) , y1+rate*(y2-y1) )。
然后就比较方便了。
【对于本题】
本题的话，就是可以按每个圆覆盖点对的前端rate值排序。
然后就很容易贪心得到每部分极长被覆盖距离。
【其它】
程序有点货不对板。。。求圆与线段的一个交点时用的直接暴力枚举，不是二分。。。
【CODE】
#include #include #include #include #include #define sqr(x) ((x)*(x))
using namespace std;
const int N=125;
const int Times=3000;
const double Start_Step=100;
const double eps=1e-6;
struct Point{int x,y;}p[N];
int n,cnt;
int R[N];
struct Line{double St,Ed;}L[N];

void op(){
for (int i=1;i<=n+2;i++) swap(p[i].x,p[i].y);
}

inline bool Cover(double x,int i){
if (x double y=p[1].y+(x-p[1].x)/(p[2].x-p[1].x)*(p[2].y-p[1].y);
return sqr(R[i])>=sqr(x-p[i].x)+sqr(y-p[i].y);
}

void work(){
n+=2;
double sx=(double)(p[2].x-p[1].x)/Times,sy=(double)(p[2].y-p[1].y)/Times;
int i,j;
cnt=0;
for (i=3;i<=n;i++){
double x=p[1].x,y=p[1].y;
for (j=0;j<=Times;j++){
if (Cover(x,i)){
cnt++;
double tx=x,ty=y,step;
for (step=Start_Step;step>eps;step/=2)
while (Cover(x-step,i)) x-=step;
L[cnt].St=x;
x=tx;
for (step=Start_Step;step>eps;step/=2)
while (Cover(x+step,i)) x+=step;
L[cnt].Ed=x;
break;
}
x+=sx; y+=sy;
}
}
}

int cmp(const void *A,const void *B){
Line AA=*((Line*)A),BB=*((Line*)B);
if (AA.St if (AA.St>BB.St) return 1;
return 0;
}

void solve(){
qsort(L+1,cnt,sizeof(Line),cmp);
double now=0,Sum=0,last;
for (int i=1;i<=cnt;i++){
if (i==1 || last Sum+=now;
now=L[i].Ed-L[i].St;
last=L[i].Ed;
}
else{
if (L[i].Ed>last){
now+=L[i].Ed-last;
last=L[i].Ed;
}
}
}
Sum+=now;
printf("%.2lfn",Sum/(p[2].x-p[1].x)*100);
}

int main(){
while (1){
scanf("%d",&n); if (!n) return 0;
scanf("%d%d%d%d",&p[1].x,&p[1].y,&p[2].x,&p[2].y);
for (int i=3;i<=n+2;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&R[i]);
if (abs(p[1].x-p[2].x) if (p[1].x>p[2].x) swap(p[1],p[2]);
work();
solve();
}
}