首页 > 代码库 > POJ 1066 Treasure Hunt (线段相交)
POJ 1066 Treasure Hunt (线段相交)
题意:给你一个100*100的正方形,再给你n条线(墙),保证线段一定在正方形内且端点在正方形边界(外墙),最后给你一个正方形内的点(保证不再墙上)
告诉你墙之间(包括外墙)围成了一些小房间,在小房间内可以从房间边界(墙)的中点走过这堵墙,问你从给定的点走到外墙外最少走过的墙数
题解:注意我们可以从每个房间的墙的中点走出,而不是一整条线段(墙)的中点走出。。。。
然后我们可以找四周的边界中的每个点与给定点的连线,再与给定的线段找相交最少的交点数就是答案
但是边界每个点是无穷多个,因此我们可以这样做:枚举每个给定线段的两个端点加外墙的四个端点
因为在外墙上每两个点之间的点不可能绕过其他的墙
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const ll INF=1ll<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=500; struct point { double x,y; }; point poi[Max],enn; double xmult(point p1,point p2,point p0)//计算 cross product (p1-p0) x (p2-p0) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } int isIntersected(point p1,point p2,point l1,point l2)//线段相交(不包括端点重合) { return (max(p1.x,p2.x)>=min(l1.x,l2.x)) && (max(p1.y,p2.y)>=min(l1.y,l2.y)) && (max(l1.x,l2.x)>=min(p1.x,p2.x)) && (max(l1.y,l2.y)>=min(p1.y,p2.y)) && (xmult(l1,p2,p1)*xmult(p2,l2,p1)>0) && (xmult(p1,l2,l1)*xmult(l2,p2,l1)>0) ; } int Solve(int n) { int minx=Inf; for(int i=0; i<n; ++i)//枚举每个端点 { int res=1; for(int j=0; j<n-4; j+=2)//每堵墙找是否有交点 { if(isIntersected(poi[i],enn,poi[j],poi[j+1])) res++; } minx=min(minx,res); } if(!n) return 1; return minx; } int main() { int n; while(~scanf("%d",&n)) { n<<=1; for(int i=0; i<n; ++i) { scanf("%lf %lf",&poi[i].x,&poi[i].y); } scanf("%lf %lf",&enn.x,&enn.y); poi[n].x=0,poi[n++].y=0; poi[n].x=0,poi[n++].y=100; poi[n].x=100,poi[n++].y=0; poi[n].x=100,poi[n++].y=100;//添加外墙四个点 printf("Number of doors = %d\n",Solve(n)); } return 0; }
POJ 1066 Treasure Hunt (线段相交)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。