首页 > 代码库 > 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;
}
View Code

 

POJ 1066 Treasure Hunt