首页 > 代码库 > POJ 1066 Treasure Hunt
POJ 1066 Treasure Hunt
题目大意:求到到目标点至少需要穿过几道墙。
题目思路:暴力循环,计算各个点(不要忘记四角)与目标点的连线穿过多少条线段,取最小值。
#include<cstdio> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f3f #define MAX 100005 using namespace std; struct node { int x1,y1,x2,y2; }point[MAX]; int n; double sx,sy; double Cross(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4) { double a=(x1-x2)*(y1-y3)-(x1-x3)*(y1-y2); double b=(x1-x2)*(y1-y4)-(x1-x4)*(y1-y2); return a*b; } int Ans(double x1,double y1,int pos) { int sum=1; for(int i=3;i<=n+2;i++) { if(pos==i) continue; if(Cross(x1,y1,sx,sy,point[i].x1,point[i].y1,point[i].x2,point[i].y2)<=1e-10 && Cross(point[i].x1,point[i].y1,point[i].x2,point[i].y2,x1,y1,sx,sy)<1e-10) sum++; } return sum; } void Solve() { int minn=INF; double x1,y1; for(int i=1;i<=n+2;i++) { x1=point[i].x1; y1=point[i].y1; int ans=Ans(x1,y1,i); minn=min(ans,minn); x1=point[i].x2; y1=point[i].y2; ans=Ans(x1,y1,i); minn=min(ans,minn); } printf("Number of doors = %d\n",minn); } int main() { while(scanf("%d",&n)!=EOF) { point[1].x1=0; point[1].y1=0; point[1].x2=100; point[1].y2=100; point[2].x1=100; point[2].y1=0; point[2].x2=0; point[2].y2=100; for(int i=3;i<=n+2;i++) { scanf("%d%d%d%d",&point[i].x1,&point[i].y1,&point[i].x2,&point[i].y2); } scanf("%lf%lf",&sx,&sy); Solve(); } return 0; }
POJ 1066 Treasure Hunt
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。