POJ 3304 判断直线与线段相交

题意：问存不存在一条直线，各个线段在直线上的投影有公共部分，也就是判断是否存在一条直线将所有线段都相交。

枚举所有端点构成的直线如果有一条直线相交所有线段那么就存在。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-8
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);
}
int main()
{
    int t,n;
    point data[405];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n*2; i+=2)
            scanf("%lf%lf%lf%lf",&data[i].x,&data[i].y,&data[i+1].x,&data[i+1].y);
        int ans=0;
        for(int i=0; i<2*n; i++)
        {
            for(int j=i+1; j<2*n; j++)
            {
                if(fabs(data[i].x-data[j].x)>eps||fabs(data[i].y-data[j].y)>eps)
                {
                    ans=1;
                    for(int k=0; k<n*2; k+=2)
                    {
                        double d1=Direction(data[i],data[j],data[k]);
                        double d2=Direction(data[i],data[j],data[k+1]);
                        if(d1*d2>0)
                        {
                            ans=0;
                            break;
                        }
                    }
                }
                if(ans)
                    break;
            }
            if(ans)
                break;
        }
        if(ans)
            puts("Yes!");
        else
            puts("No!");
    }
    return 0;
}