2015
05-23

Shooting

There are some key points in a plane that can absorb everything inside the plane. The problem is, “A gun is shooting the plane, what’s the probability for the bullets to be absorbed by each key point”?
The plane is a rectangle whose height and width equals 1. Points in plane can be defined as ( x, y ), 0 < x < 1 , 0 < y < 1. When shooting, the bullets follow the distribution below:

After a bullet falls into the plane, it will be absorbed by the nearest key point. You are given the position of every key point. Can you tell me the probability absorbed by them?

The first line contains a single integer T (T <= 100), the number of test cases.

For each case, the first line of each case is a integer n(n <= 100), n means the number of key points.
Following n lines, each line contains two number a and b, (a , b) means the position of a key point.

The first line contains a single integer T (T <= 100), the number of test cases.

For each case, the first line of each case is a integer n(n <= 100), n means the number of key points.
Following n lines, each line contains two number a and b, (a , b) means the position of a key point.

2
1
0.5 0.5
2
0.25 0.5
0.75 0.5

Case #1:
1.000000
Case #2:
0.625000
0.375000
Hint
Recommend eps equal or smaller than 1e-11.


ps：半平面交学习的话可以去这里，写的很好

#include <cmath>
#include <cstdio>
#include<algorithm>
using namespace std;
const  double INF = 1000000000.0;
const  int maxn = 1010;
const double eps = 1e-12;
inline double sgn(double x) {return fabs(x)<eps?0:(x>0?1:-1);}
struct Point{
double x,y;
Point(double tx=0,double ty=0){x=tx;y=ty;}
bool operator == (const Point& t) const {
return sgn(x-t.x)==0 && sgn(y-t.y)==0;
}
Point operator - (const Point& t) const {
Point tmp;
tmp.x = x - t.x;
tmp.y = y - t.y;
return tmp;
}
}p[maxn],tmp[maxn],pp[maxn],GP;
struct Seg{Point s,e;};
struct Line {
double a, b, c;
};//中垂线
double cross(Point a,Point b,Point c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
inline Point intersect(Point x,Point y,double a,double b,double c){
double u = fabs(a * x.x + b * x.y + c);
double v = fabs(a * y.x + b * y.y + c);
return Point( (x.x * v + y.x * u) / (u + v) , (x.y * v + y.y * u) / (u + v) );
}
int n,ban_tot;
void CUT1(double a,double b,double c){//points must be clockwise    a*x+b*y+c>=0表示点在半平面内
int i,tot=0;
for(int i = 1; i <= ban_tot; ++i){
if(a*p[i].x + b*p[i].y + c >= eps) pp[++tot] = p[i];
else {
if(a*p[i-1].x + b*p[i-1].y + c > eps){
pp[++tot] = intersect(p[i],p[i-1],a,b,c);
}
if(a*p[i+1].x + b*p[i+1].y + c > eps){
pp[++tot] = intersect(p[i],p[i+1],a,b,c);
}
}
}  ban_tot=tot;
pp[tot+1]=pp[1];pp[0]=pp[tot];
memcpy(p,pp,sizeof(pp));
}
void CUT2(double a,double b,double c){//a*x+b*y+c<=0表示点在半平面内
int i,tot=0;
for(int i = 1; i <= ban_tot; ++i){
if(!(a*p[i].x + b*p[i].y + c > eps) ) pp[++tot] = p[i]; //点在半平面内或者边界上
else {
if(a*p[i-1].x + b*p[i-1].y + c < -eps){  //上个点完全在半平面内
pp[++tot] = intersect(p[i],p[i-1],a,b,c);
}
if(a*p[i+1].x + b*p[i+1].y + c < -eps){  //下个点完全在半平面内
pp[++tot] = intersect(p[i],p[i+1],a,b,c);
}
}
}  ban_tot=tot;
pp[tot+1]=pp[1];pp[0]=pp[tot];//两端都扩展一个点
memcpy(p,pp,sizeof(pp));
}
Line Turn(Point s, Point e) {                                        // 线段转直线表达式
Line ln;
ln.a = s.y - e.y;
ln.b = e.x - s.x;
ln.c = s.x*e.y - e.x*s.y;
return ln;
}
Line make(Point a,Point b)//求a,b中垂线的直线方程
{
double x0=(a.x+b.x)/2;
double y0=(a.y+b.y)/2;
Line tmp=Turn(a,b);
Line ans;
ans.a=tmp.b;
ans.b=-tmp.a;
ans.c=tmp.a*y0-tmp.b*x0;
return ans;
}
Line ln[maxn];
inline double PPdis(Point a, Point b) {                                // 点点距离
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double PLdis(Point p,Point l1,Point l2){                        // 点线距离
return fabs(cross(p,l1,l2))/PPdis(l1,l2);
}
double calc(Point *p,int n)
{
if(n<3) return 0;
double area=0,V=0;
for(int i=0;i<n;i++) area+=p[(i+1)%n].y*(p[i].x-p[(i+2)%n].x);
area/=2;
area=fabs(area);
double H=10;
int pos=0;
for(int i=0;i<n;i++)
{
if(2-p[i].x-p[i].y<H)
{
H=2-p[i].x-p[i].y;
pos=i;
}
}
V+=area*H;
for(int i=pos+1;;i++)
{
int id1=i%n;
int id2=(i+1)%n;
if(id2==pos) break;
double h=PLdis(p[pos],p[id1],p[id2]);
double s=((2-p[id1].x-p[id1].y-H) + (2-p[id2].x-p[id2].y-H)) * PPdis(p[id1],p[id2])/2;
V+=s*h/3;
}
return V;
}
double ans[110];
int main(){
int t,ca=1,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&tmp[i].x,&tmp[i].y);
for(int i=1;i<=n;i++)
{
p[1]=Point(0,0);
p[2]=Point(0,1);
p[3]=Point(1,1);
p[4]=Point(1,0);
p[0]=p[4];
p[5]=p[1];//首尾都要加上一个点，保证边界的合法点不会漏掉
ban_tot=4;
double x0=tmp[i].x,y0=tmp[i].y;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
Line mid_line = make(tmp[i],tmp[j]);
double a=mid_line.a,b=mid_line.b,c=mid_line.c;
if(a*x0+b*y0+c >= eps)
{
CUT1(a,b,c);
}
else
{
CUT2(a,b,c);
}
}
double tmpv=calc(p,ban_tot);
ans[i]=tmpv;
}
printf("Case #%d:\n",ca++);
for(int i=1;i<=n;i++)
{
printf("%.6lf\n",ans[i]);
}
}
return 0;
}