题目：http://poj.org/problem?id=3304
Description
Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.1.0 1.0 2.0 1.0
No!
求是否存在一条直线可以与列出的所有线段相交。
解题：如果存在这么一条直线，必定过平面中的两个点，
所以任意穷举两个点所在的直线与所有线段判断是否相交。
这道题还有注意精度问题。
#include <iostream>
#define MAX 201
using namespace std;
int n;
// 精度判定
const double eps = 1E-8;
int sig(double d)
{
return (d>eps) - (d<-eps);
}
struct Point
{
double x,y;
}point[MAX];
double cross(Point &o,Point& a,Point &b)
{
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
//判断直线ab是否与线段cd相交
//0 不相交
//1 规范相交
//2 不规范相交
int segLineCross(Point &a,Point &b,Point &c,Point &d)
{
int d1,d2;
d1 = sig(cross(a,b,c));
d2 = sig(cross(a,b,d));
if((d1^d2)==-2)//注意加小括号，^的优先级比==低
return 1;
if(d1==0 || d2==0)
return 2;
return 0;
}
bool Test(Point &a,Point &b)//判断直线ab是否与所有线段相交
{
int i;
if(sig(a.x-b.x)==0 && sig(a.y-b.y)==0)//★判断重复点
return false;
for(i=0;i<2*n;i+=2)
if(segLineCross(a,b,point[i],point[i+1])==0)
return false;
return true;
}
bool Find()
{
int i,j;
for(i=0;i<2*n;++i)
for(j=0;j<2*n;++j)
if(Test(point[i],point[j]))
return true;
return false;
}
int main()
{
int test,i;
cin >> test;
while(test--)
{
cin >> n;
for(i=0;i<2*n;++i)
cin>>point[i].x>>point[i].y;
if(Find())
cout << "Yes!" << endl;
else
cout << "No!" << endl;
}
return 0;
}
ACM-计算几何之Segments——poj3304,布布扣,bubuko.com
原文：http://blog.csdn.net/lttree/article/details/23788215