POJ 3304 /// 判断线段与直线是否相交

题目大意：

询问给定n条线段 是否存在一条直线使得所有线段在直线上的投影存在公共点

这个问题可以转化为 是否存在一条直线与所有的线段同时相交

而枚举直线的问题

因为若存在符合要求的直线 那么必存在穿过某线段的端点的直线是符合要求的直线

那么只要枚举两个端点连成一线

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
const double eps=1e-10;
double add(double a,double b) {
    if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
    return a+b;
} // 考虑误差
struct P {
    double x,y;
    P(){};
    P(double _x,double _y):x(_x),y(_y){}
    P operator - (P p) {
        return P(add(x,-p.x),add(y,-p.y)); }
    P operator + (P p) {
        return P(add(x,p.x),add(y,p.y)); }
    P operator * (double d) {
        return P(x*d,y*d); }
    double dot(P p) { // 点积
        return add(x*p.x,y*p.y); }
    double det(P p) { // 叉积
        return add(x*p.y,-y*p.x); }
}p[105],q[105];
int n;
/* 计算ab两点的距离
设点a(x1,y1) b(x2,y2)
则dis=sqrt((x1-x2)^2+(y1-y2)^2)
设 c=a-b=(x1-x2,y1-y2)
那么 c的点积恰好等于距离的平方
*/
double dis(P a,P b) {
    return sqrt((a-b).dot(a-b));
}
/*判断线段S与直线L是否相交
(l1-s1)与(l2-s1)的叉积可以判断两向量的相对位置
叉积>0说明前者在后者的顺时针方向（s1在l1l2的右边）
叉积<0说明前者在后者的逆时针方向（s1在l1l2的左边）
那么两个端点对应的叉积相乘小于0
就说明两个端点在直线的不同侧
即线段与直线相交
*/
bool insSL(P s1,P s2,P l1,P l2) {
    return (l1-s1).det(l2-s1)*
            (l1-s2).det(l2-s2) <=0;
}
bool check(P a,P b)
{
    if(dis(a,b)==0) return 0; // 同一点
    for(int i=0;i<n;i++)
        if(insSL(p[i],q[i],a,b)==0) return 0; // 存在不相交
    return 1; // 与所有线段都相交
}
void solve()
{
    bool flag=0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(check(p[i],p[j]) || check(p[i],q[j])
               || check(q[i],p[j]) || check(q[i],q[j]))
            { flag=1; break; }
        }
        if(flag) break;
    }
    if(flag) printf("Yes!
");
    else printf("No!
");
}
int main()
{
    int t; scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&q[i].x,&q[i].y);
        solve();
    }
}