【POJ】1066 Treasure Hunt

2024-01-30 03:08

文章标签 poj 1066 treasure hunt

本文主要是介绍【POJ】1066 Treasure Hunt，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Treasure Hunt

Link

在这里插入图片描述
懒得翻了。

解题思路

将宝藏点和所有线段的端点（包括矩形的四个顶点）连接，穿过的线段数就是要经过的线段数。

code

#include<iostream>
#include<cstdio>
using namespace std;int n,ans=0x3f3f3f3f;struct abc{double x,y,xx,yy;
}a[40],ts;struct abcd{double x,y;friend bool operator == (abcd p,abcd q){return p.x==q.x&&p.y==q.y;}
};int cj(abcd b1,abcd b2,abcd b3)
{return (b1.x-b3.x)*(b2.y-b3.y)-(b2.x-b3.x)*(b1.y-b3.y);
}int online(abcd b1,abcd b2,abcd b3)
{if(b3.x>=min(b1.x,b2.x)&&b3.x<=max(b1.x,b2.x)&&b3.y>=min(b1.y,b2.y)&&b3.y<=max(b1.y,b2.y))return 1;return 0;
}int check(abc x,abc y)
{abcd a1,a2,a3,a4;a1.x=x.x,a1.y=x.y;a2.x=x.xx,a2.y=x.yy;a3.x=y.x,a3.y=y.y;a4.x=y.xx,a4.y=y.yy;if(a1==a3||a1==a4||a2==a3||a2==a4)return 0;if(cj(a1,a2,a3)*cj(a1,a2,a4)<0&&cj(a3,a4,a1)*cj(a3,a4,a2)<0) return 1;if(cj(a1,a2,a3)==0&&online(a1,a2,a3)) return 1;if(cj(a1,a2,a4)==0&&online(a1,a2,a4)) return 1;if(cj(a3,a4,a1)==0&&online(a3,a4,a1)) return 1;if(cj(a3,a4,a2)==0&&online(a3,a4,a1)) return 1;return 0;
}int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].xx,&a[i].yy);a[n+1].x=0,a[n+1].y=100,a[n+1].xx=100,a[n+1].yy=0;scanf("%lf%lf",&ts.x,&ts.y);for(int i=1;i<=n+1;i++){int s=0;ts.xx=a[i].x,ts.yy=a[i].y;for(int j=1;j<=n;j++)if(check(a[j],ts))s++;ans=min(ans,s);s=0;ts.xx=a[i].xx,ts.yy=a[i].yy;for(int j=1;j<=n;j++)if(check(a[j],ts))s++;ans=min(ans,s);}printf("Number of doors = %d\n",ans+1);
}