POJ 1066 Treasure Hunt

╰+攻爆jí腚メ 2022-05-18 06:08 141阅读 0赞

题意：在金字塔内有一个宝藏p(x,y)。现在要取出这个宝藏，在金字塔内有许多面墙，为了进入宝藏所在的位置必须把墙炸开，炸墙只能炸每个房间墙的中点，求将宝藏运出城堡所需要的最小炸墙数。

分析：虽然炸墙只能炸中点，但是因为每个房间里面是空的，而且关心的是最少要炸几面墙，金字塔范围因为只有100\*100，所以直接枚举边上的每个点与宝藏的连线，与墙的交点个数最少的直线，就是炸墙的路线。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include <iomanip>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 35;
    const double eps = 1e-8;
    int n;
    
    struct Point{
        double x,y;
        Point(){}
        Point(double _x,double _y){x=_x;y=_y;}
    }trea;
    
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){s=_s;e=_e;}
    }line[maxn];
    
    int sgn(double x)
    {
        if(fabs(x)<eps) return 0;
        else return x<0?-1:1;
    }
    
    double cross(Point a,Point b,Point c)
    {
        a.x-=c.x;a.y-=c.y;
        b.x-=c.x;b.y-=c.y;
        return a.x*b.y-b.x*a.y;
    }
    
    bool intersect(Line l1,Line l2)
    {
        int d1=sgn(cross(l1.s,l2.s,l2.e));
        int d2=sgn(cross(l1.e,l2.s,l2.e));
        int d3=sgn(cross(l2.e,l1.s,l1.e));
        int d4=sgn(cross(l2.s,l1.s,l1.e));
        if(d1*d2<0&&d3*d4<0)
            return true;
        return false;
    }
    
    int slove(Line l1)
    {
        int ret=0;
        for(int i=1;i<=n;i++)
            if(intersect(l1,line[i]))
                ret++;
        return ret;
    }
    
    int main()
    {
        double x1,y1,x2,y2;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[i]=Line(Point(x1,y1),Point(x2,y2));
        }
        scanf("%lf%lf",&trea.x,&trea.y);
        Line t;
        int ans=inf;
        for(int i=1;i<=100;i++)
        {
            t.s=trea;
            t.e.x=i,t.e.y=0,ans=min(ans,slove(t));
            t.e.x=i,t.e.y=100,ans=min(ans,slove(t));
            t.e.x=0,t.e.y=i,ans=min(ans,slove(t));
            t.e.x=100,t.e.y=i,ans=min(ans,slove(t));
        }
        printf("Number of doors = %d\n",ans+1);
        return 0;
    }