//枚举4条边界的点a，然后求线段out(trea,a)与其他wall相交的最小数
//代码中的max改为min有助理解
#include<iostream>
using namespace std;
#define MAXN 30
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point
{double x,y;};
struct line{point a,b;};
line wall[MAXN+1];
int n;
point trea;
//计算cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//判两点在线段异侧,点在线段上返回0
int opposite_side(point p1,point p2,line l){
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps;
}
//判两线段相交,不包括端点和部分重合
int intersect_ex(line u,line v){
return opposite_side(u.a,u.b,v)&&opposite_side(v.a,v.b,u);
}
int main()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf%lf%lf",&(wall[i].a.x),&(wall[i].a.y),&(wall[i].b.x),&(wall[i].b.y));
scanf("%lf%lf",&(trea.x),&(trea.y));
line out;
out.a=trea;
int max=n+1;
double x,y;
for(x=0,out.b.y=100;x<=100;x+=0.01)
{
out.b.x=x;
int t=0;
for(i=0;i<n;i++)
if(intersect_ex(out,wall[i]))
t++;
if(t<max) max=t;
}
for(x=0,out.b.y=0;x<=100;x+=0.01)
{
out.b.x=x;
int t=0;
for(i=0;i<n;i++)
if(intersect_ex(out,wall[i]))
t++;
if(t<max) max=t;
}
for(y=0,out.b.x=0;y<=100;y+=0.01)
{
out.b.y=y;
int t=0;
for(i=0;i<n;i++)
if(intersect_ex(out,wall[i]))
t++;
if(t<max) max=t;
}
for(y=0,out.b.x=100;y<=100;y+=0.01)
{
out.b.y=y;
int t=0;
for(i=0;i<n;i++)
if(intersect_ex(out,wall[i]))
t++;
if(t<max) max=t;
}
printf("Number of doors = %d\n",max+1);
return 0;
}posted on 2009-10-05 15:05
wyiu 阅读(120)
评论(0) 编辑 收藏 引用 所属分类:
POJ