题目地址：http://poj.org/problem?id=3304
任意枚举两点组成的线段是否能与所有线段相交
判断相交的办法是叉积小于等于零，但在叉积之前要排除掉两个一样的点，因为零向量与任何向量叉积都为0
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const double EPS=1e-8;
bool IsZero(double x){ //判断x是否为零 return -EPS<x&&x<EPS;
}
#define Vector Point
struct Point{double x,y;Point(double x,double y):x(x),y(y){};Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}
};
vector<Point> points;double cross(Vector s1,Vector s2){return s1.x*s2.y-s1.y*s2.x;
}
double dist(Point p1,Point p2){return hypot(fabs(p1.x-p2.x),fabs(p1.y-p2.y));
}
bool solved(int i,int j){Point p1=points[i],p2=points[j];if(IsZero(dist(p1,p2))) return false; //一定要写，不写会错 ，因为一个点与任何线叉乘都为0 for(int k=0;k<points.size();k++){if(k==i||k==j||(k%2==0?k+1:k-1)==i||(k%2==0?k+1:k-1)==j) continue;Point p3=points[k],p4=points[(k%2==0?k+1:k-1)];if(cross(p2-p1,p3-p1)*cross(p2-p1,p4-p1) > EPS) return false;}return true;
}int main()
{int T;cin>>T;while(T--){int n;double x1,y1,x2,y2;points.clear();cin>>n;while(n--) {scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);points.push_back(Point(x1,y1));points.push_back(Point(x2,y2));}int ok=1;if(n!=1)for(int i=0;i<points.size()-1;i++){for(int j=i+1;j<points.size();j++){ok=0;if(solved(i,j)) ok=1;if(ok) break;}if(ok) break;}cout<<(ok?"Yes!":"No!")<<endl;}return 0;
}