首页 > 代码库 > POJ 1066 Treasure Hunt 线段相交判断
POJ 1066 Treasure Hunt 线段相交判断
判断以宝藏的坐标和中点的坐标为线段的点是否与墙相交,求最少相交的墙的数量
中点算出来,枚举中点和墙
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define eps 1e-8#define INF 1e9using namespace std;const int maxn=100;typedef struct Point{ double x,y; Point() {}; Point(double xx,double yy) { x=xx; y=yy; }} Vector;struct Line{ Point p,q; Line() {}; Line(Point pp,Point qq) { p=pp; q=qq; }};int sgn(double x){ if(fabs(x)<eps) return 0; return x<0? -1:1;}double crs_prdct(Vector a,Vector b){ return a.x*b.y-b.x*a.y;}double dot_prdct(Vector a,Vector b){ return a.x*a.y+b.x*b.y;}Point mid_point(Point a,Point b){ return Point((a.x+b.x)/2,(a.y+b.y)/2);}Vector operator - (Point a,Point b){ return Vector(a.x-b.x,a.y-b.y);}bool operator == (Point a,Point b){ return a.x==b.x && a.y==b.y;}bool inter(Line l1,Line l2){ return max(l1.p.x,l1.q.x) >= min(l2.p.x,l2.q.x) && max(l2.p.x,l2.q.x) >= min(l1.p.x,l1.q.x) && max(l1.p.y,l1.q.y) >= min(l2.p.y,l2.q.y) && max(l2.p.y,l2.q.y) >= min(l1.p.y,l1.q.y) && sgn(crs_prdct(l2.p-l1.p,l1.q-l1.p))*sgn(crs_prdct(l2.q-l1.p,l1.q-l1.p))<=0 && sgn(crs_prdct(l1.p-l2.p,l2.q-l1.p))*sgn(crs_prdct(l1.q-l2.p,l2.q-l2.p))<=0;}bool cmp(Point a,Point b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x;}Line line[maxn];Point mid[4*maxn];Point a[4][maxn];int main(){// freopen("in.txt","r",stdin); int n; while(scanf("%d",&n)!=EOF) { double x1,y1,x2,y2; for(int i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[i]=Line(Point(x1,y1),Point(x2,y2)); } Point p; scanf("%lf%lf",&p.x,&p.y); a[0][0]=Point(0,0); a[1][0]=Point(0,0); a[2][0]=Point(0,100); a[3][0]=Point(100,0); int cnt[4]={1,1,1,1}; for(int i=0;i<n;i++) { if(line[i].p.y==0) a[0][cnt[0]++]=Point(line[i].p.x,0); if(line[i].q.y==0) a[0][cnt[0]++]=Point(line[i].q.x,0); if(line[i].p.x==0) a[1][cnt[1]++]=Point(0,line[i].p.y); if(line[i].q.x==0) a[1][cnt[1]++]=Point(0,line[i].q.y); if(line[i].p.y==100) a[2][cnt[2]++]=Point(line[i].p.x,100); if(line[i].q.y==100) a[2][cnt[2]++]=Point(line[i].q.x,100); if(line[i].p.x==100) a[3][cnt[3]++]=Point(100,line[i].p.y); if(line[i].q.x==100) a[3][cnt[3]++]=Point(100,line[i].q.y); } a[0][cnt[0]++]=Point(100,0); a[1][cnt[1]++]=Point(0,100); a[2][cnt[2]++]=Point(100,100); a[3][cnt[3]++]=Point(100,100); for(int i=0;i<4;i++) sort(a[i],a[i]+cnt[i],cmp); int cnt2=0; for(int i=0;i<4;i++) for(int j=0;j<cnt[i]-1;j++) if(!(a[i][j]==a[i][j+1])) mid[cnt2++]=mid_point(a[i][j],a[i][j+1]); int ans=INF; for(int i=0;i<cnt2;i++) { int tmp=0; for(int j=0;j<n;j++) if(inter(Line(p,mid[i]),line[j])) tmp++; ans=min(ans,tmp); } printf("Number of doors = %d \n",ans+1); } return 0;}
POJ 1066 Treasure Hunt 线段相交判断
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。