POJ 1066 Treasure Hunt（计算几何）

题意：给出一个100*100的正方形区域，通过若干连接区域边界的线段将正方形区域分割为多个不规则多边形小区域，然后给出宝藏位置，要求从区域外部开辟到宝藏所在位置的一条路径，使得开辟路径所需要打通的墙壁数最少("打通一堵墙"即在墙壁所在线段中间位置开一空间以连通外界)，输出应打通墙壁的个数(包括边界上墙壁)。
题解：枚举每一个入口，在所有的情况中取穿墙数最少的输出即可，枚举每一个入口的时候，并不用枚举每条边的中间点，直接枚举该线段的两个顶点就行(因为要经过一个墙，那么从线段的任意地方进去都行，不必要每次从线段的中点过去)，将枚举的顶点与终点(即宝藏所在位置)连成线段，然后就是判断剩下的线段与该线段相交的问题了(注意这里是严格相交)，最后得出的数字加1即为结果(因为还有边界墙)，还有就是需要特别处理n=0时的情况。

个人感觉，计算几何简单的题就是模版的事，只要记住这几个常用模板（叉积，线段相交，Point，Line）一般的计算几何就没问题了。

AC代码：

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

typedef unsigned long long ull;

#define prN printf("\n")

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const int MAX_N= 1000+5 ;

const double eps= 1e-9 ;

int sgn(double x)

{

    if(fabs(x) < eps)return 0;

    if(x < 0) return -1;

    else return 1;

}

struct Point

{

    double x,y;

    Point() {}

    Point(double _x,double _y)

    {

        x = _x;

        y = _y;

    }

    Point operator -(const Point &b)const

    {

        return Point(x - b.x,y - b.y);

    }

    double operator ^(const Point &b)const

    {

        return x*b.y - y*b.x;

    }

    double operator *(const Point &b)const

    {

        return x*b.x + y*b.y;

    }

};

struct Line

{

    Point s,e;

    Line() {}

    Line(Point _s,Point _e)

    {

        s = _s;

        e = _e;

    }

};

bool inter(Line l1,Line l2)

{

　　//这要多判断一步，是否是边界点，因为遍历就是从边界开始的，所以要除掉2个端点

    if (fabs(l1.s.x-l2.s.x)<eps&&fabs(l1.s.y-l2.s.y)<eps||fabs(l1.s.x-l2.e.x)<eps&&fabs(l1.s.y-l2.e.y)<eps)

        return false;

    return

        max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&

        max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&

        max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&

        max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&

        sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&

        sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0;

}

double dist(Point a,Point b)

{

    return sqrt((b-a)*(b-a));

}

Line line[35];

Point po[65];

int n,num,res=INF;

double endx,endy;

void sol()

{

    if (n==0)

    {

        puts("Number of doors = 1");

        return;

    }

    rep(i,num)

    {

        int ans=0;

        Line tel(po[i],Point(endx,endy));

        rep(j,n)

        {

            if (inter(tel,line[j]))

            {

                ans++;

            }

        }

        res=min(ans,res);

    }

    printf("Number of doors = %d\n",res+1);

}

int main()

{

    double x1,y1,x2,y2;

    SI(n);

    rep(i,n)

    {

        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

        po[num++]=Point(x1,y1);

        po[num++]=Point(x2,y2);

        line[i]=Line(Point(x1,y1),Point(x2,y2));

    }

    scanf("%lf%lf",&endx,&endy);

    sol();

    return 0;

}

巴特西

POJ 1066 Treasure Hunt（计算几何）

最新文章

热门文章