POJ 1066 判断线段相交

题意：有个考古队进金字塔里盗墓，大小100*100，样图是一个俯视图，给了财宝坐标，又给了各个墙。题目规定考古队在每面墙的中点处开一个洞，这样就避免了两墙交点的情况，求最小的凿墙数目。

很明显，枚举连接四面两个墙之间中点与宝藏的线段，求出这种线段与墓里墙相交的最小值。其实可以不用枚举中点，直接用墙的端点与宝藏相连的线段就行，细想一想可以想明白。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double PointType;
struct point
{
    PointType x,y;
};
PointType Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
bool On_Segment(point pi,point pj,point pk)
{
    if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
        return 1;
    return 0;
}
bool Segment_Intersect(point p1,point p2,point p3,point p4)
{
    PointType d1=Direction(p3,p4,p1),d2=Direction(p3,p4,p2),d3=Direction(p1,p2,p3),d4=Direction(p1,p2,p4);
    if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0)))
        return 1;
    if(d1==0&&On_Segment(p3,p4,p1))
        return 1;
    if(d2==0&&On_Segment(p3,p4,p2))
        return 1;
    if(d3==0&&On_Segment(p1,p2,p3))
        return 1;
    if(d4==0&&On_Segment(p1,p2,p4))
        return 1;
    return 0;
}
double x1[10000],x2[10000],y1[10000],y2[10000];
int w,nx1,nx2,ny1,ny2;
point data[10000][2];
void zx(double m,double n)
{
    if(m==0)
    {
        y1[ny1++]=n;
        return;
    }
    if(m==100)
    {
        y2[ny2++]=n;
        return;
    }
    if(n==0)
    {
        x1[nx1++]=m;
        return;
    }
    if(n==100)
    {
        x2[nx2++]=m;
        return;
    }
}
int main()
{
    while(~scanf("%d",&w))
    {
        nx1=nx2=ny1=ny2=0;
        double m,n;
        for(int i=0; i<w; i++)
        {
            scanf("%lf%lf",&m,&n);
            zx(m,n),data[i][0].x=m,data[i][0].y=n;
            scanf("%lf%lf",&m,&n);
            zx(m,n),data[i][1].x=m,data[i][1].y=n;
        }
        point temp,t;
        scanf("%lf%lf",&t.x,&t.y);
        if(w==0)
        {
            puts("Number of doors = 1");
            continue;
        }
        int sum=9999999;
        for(int i=0; i<ny1; i++)
        {
            temp.x=0,temp.y=y1[i];
            int num=1;
            for(int j=0; j<w; j++)
                if(Segment_Intersect(data[j][0],data[j][1],temp,t)&&(data[j][0].y!=temp.y&&data[j][1].y!=temp.y))
                    num++;
            sum=min(sum,num);
        }
        for(int i=0; i<ny2; i++)
        {
            temp.x=100,temp.y=y2[i];
            int num=1;
            for(int j=0; j<w; j++)
                if(Segment_Intersect(data[j][0],data[j][1],temp,t)&&(data[j][0].y!=temp.y&&data[j][1].y!=temp.y))
                    num++;
            sum=min(sum,num);
        }
        for(int i=0; i<nx1; i++)
        {
            temp.x=x1[i],temp.y=0;
            int num=1;
            for(int j=0; j<w; j++)
                if(Segment_Intersect(data[j][0],data[j][1],temp,t)&&(data[j][0].x!=temp.x&&data[j][1].x!=temp.x))
                    num++;
            sum=min(sum,num);
        }
        for(int i=0; i<nx2; i++)
        {
            temp.x=x2[i],temp.y=100;
            int num=1;
            for(int j=0; j<w; j++)
                if(Segment_Intersect(data[j][0],data[j][1],temp,t)&&(data[j][0].x!=temp.x&&data[j][1].x!=temp.x))
                    num++;
            sum=min(sum,num);
        }
        printf("Number of doors = %d\n",sum);
    }
    return 0;
}