[poj] 1066 Treasure Hunt || 判断直线相交

原题

在金字塔内有一个宝藏p(x,y)，现在要取出这个宝藏。

在金字塔内有许多墙，为了进入宝藏所在的房间必须把墙炸开，但是炸墙只能炸每个房间墙的中点。

求将宝藏运出城堡所需要的最小炸墙数。

---

判断点和直线相交。

枚举每道墙的两个端点和p的连线这条线段和墙的交点的次数最小值即为需要炸墙的最小次数。

【注意当墙数为零时输出1；】

#include<cstdio>

#include<algorithm>

#define N 33

using namespace std;

int ans=0x3f3f3f3f,n;

struct point

{

    double x,y;

    point() {}

    point(double _x,double _y) : x(_x),y(_y) {}

    point operator - (const point &b) const

	{

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

	}

    double operator * (const point &b) const

	{

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

	}

    bool operator == (const point &b) const

	{

	    return x==b.x && y==b.y;

	}

}p[2*N],end;

int intersect(point a,point b)//相交

{

    int ans=0;

    if (a==b) return 0;

    for (int i=1;i<=n;i++)

	if (((a-p[i])*(a-b))*((a-p[i+n])*(a-b))<=0 && (p[i]-a)*(p[i]-p[i+n])*((p[i]-b)*(p[i]-p[i+n]))<=0)

	    ans++;

    return ans;

}

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;i++)

	scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);

    scanf("%lf%lf",&end.x,&end.y);

    if (!n)

    {

	puts("Number of doors = 1");

	return 0;

    }

    for (int i=1;i<=2*n;i++)

	ans=min(ans,intersect(p[i],end));

    printf("Number of doors = %d\n",ans);

    return 0;

}