POJ 1066 Treasure Hunt

枚举+判断线段相交

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

const int INF=0x7FFFFFFF;
const int maxn=30+10;
#define EPS 1e-8
int n,ans,num;
double Px,Py;
struct Line
{
    double Sx,Sy;
    double Ex,Ey;
} L[maxn];
struct Point
{
    double x;
    double y;
    Point(double a,double b)
    {
        x=a;
        y=b;
    }
};

double cross_pro(Point p0, Point p1, Point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
int dblcmp(double d)
{
    if (fabs(d) < EPS)
        return 0;
    return (d > 0) ? 1 : -1;
}
bool is_intersect(Point p1, Point p2, Point p3, Point p4)
{
    return dblcmp(cross_pro(p3, p4, p1)) * dblcmp(cross_pro(p3, p4, p2)) == -1;
}

int main()
{
    while(~scanf("%d",&n))
    {
        ans=INF;
        for(int i=1; i<=n; i++)
            scanf("%lf%lf%lf%lf",&L[i].Sx,&L[i].Sy,&L[i].Ex,&L[i].Ey);

        scanf("%lf%lf",&Px,&Py);

        for(int i=1; i<=n; i++)
        {
            Point A(L[i].Sx,L[i].Sy);
            Point B(Px,Py);

            num=0;
            for(int j=1; j<=n; j++)
            {
                Point C(L[j].Sx,L[j].Sy);
                Point D(L[j].Ex,L[j].Ey);
                if(is_intersect(A,B,C,D)) num++;
            }
            ans=min(ans,num);

            Point AA(L[i].Ex,L[i].Ey);
            Point BB(Px,Py);

            num=0;
            for(int j=1; j<=n; j++)
            {
                Point C(L[j].Sx,L[j].Sy);
                Point D(L[j].Ex,L[j].Ey);
                if(is_intersect(AA,BB,C,D)) num++;
            }
            ans=min(ans,num);
        }
        if(n==0) printf("Number of doors = 1
");
        else printf("Number of doors = %d
",ans+1);
    }
    return 0;
}