计算几何基础 Treasure Hunt POJ - 1066【线段相交】

这个思路确实没有想到，直接把每个点和终点连起来看与线段相交的个数就可以了？

注意n=0的情况

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=100;
const double eps=1e-8;
typedef long long ll;
struct point
{
    double x,y;
    point(double _X=0,double _Y=0)
    {
        x=_X;y=_Y;
    }
    point operator - (const point &oth)const
    {
        return point(x-oth.x,y-oth.y);
    }
        point operator + (const point &oth)const
    {
        return point(x+oth.x,y+oth.y);
    }
        point operator * (const double oth)const
    {
        return point(x*oth,y*oth);
    }
        point operator / (const double oth)const
    {
        return point(x/oth,y/oth);
    }
};
int dcmp(double x)
{
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}
double cross(point a,point b)
{
    return a.x*b.y-b.x*a.y;
}
bool segment(point a,point b,point c,point d)
{
    double c1 = cross(b-a,c-a),c2 = cross(b-a,d-a);
    double d1 = cross(d-c,a-c),d2 = cross(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;
}
pair <point,point>seg[maxn];
vector<point>p;
int idx;
point p0;
int check(point t)
{
    int ans=0;
    for(int i=0;i<idx;i++)
    {
        point a,b;
        a=seg[i].first;
        b=seg[i].second;
        if(a.x==t.x&&a.y==t.y)continue;
        if(b.x==t.x&&b.y==t.y)continue;
        if(segment(t,p0,a,b)) ans++;
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    idx=0;
    for(int i=1;i<=n;i++)
    {
        double x1,y1,x2,y2;
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        point a,b;
        a=point(x1,y1);
        b=point(x2,y2);
        p.push_back(a);
        p.push_back(b);
        seg[idx++]=make_pair(a,b);
    }
    scanf("%lf%lf",&p0.x,&p0.y);
    int all = 0x3f3f3f3f;
    for(int i=0;i<p.size();i++)
    {
        all=min(all,check(p[i]));
    }
    if(n==0) all=0;
    printf("Number of doors = %d\n",all+1);
    return 0;
}