POJ 3304 Segments
题意：给定n（n<=100）条线段，问你是否存在这样的一条直线，使得所有线段投影下去后，至少都有一个交点。
思路：对于投影在所求直线上面的相交阴影，我们可以在那里作一条线，那么这条线就和所有线段都至少有一个交点，所以如果有一条直线和所有线段都有交点的话，那么就一定有解。
怎么确定有没直线和所有线段都相交？怎么枚举这样的直线？思路就是固定两个点，这两个点在所有线段上任意取就可以，然后以这两个点作为直线，去判断其他线段即可。为什么呢？因为如果有直线和所有线段都相交，那么我绝对可以平移到某个极限的端点位置，再旋转到某个极限的端点位置，也不会失去正解。Bug点就是枚举的两个点是重点的话，这个直线的方向向量是0向量，这样会判断到与所有线段都相交。~~
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string> const int maxn = +;
struct coor
{
double x,y;
coor(){}
coor(double xx,double yy):x(xx),y(yy){}
double operator ^(coor rhs) const //计算叉积（向量积）
{
return x*rhs.y - y*rhs.x;
}
coor operator -(coor rhs) const //坐标相减，a-b得到向量ba
{
return coor(x-rhs.x,y-rhs.y);
}
double operator *(coor rhs) const //数量积
{
return x*rhs.x + y*rhs.y;
}
};
const double eps = 1e-;
struct Line
{
coor point1,point2;
Line(){}
Line(coor xx,coor yy):point1(xx),point2(yy){}
bool operator &(Line rhs) const //判断直线和rhs线段是否相交
{
//自己表示一条直线，然而rhs表示的是线段
//思路，判断rhs线段上两个端点是否在this直线的同一侧即可，用一侧，就不相交
coor ff1 = point2 - point1; //直线的方向向量
return ( ((rhs.point1-point1)^ff1) * ((rhs.point2-point1)^ff1) ) <= ;//符号不同或者有0，证明相交
}
}a[maxn];
int n; bool same (double a,double b)
{
return fabs(a-b)<eps;
}
bool check (coor aa,coor bb)
{
Line t = Line(aa,bb);
for (int i=;i<=n;++i)
{
if (!(t&a[i]))
{
return false;
}
}
return true;
}
void work ()
{
scanf("%d",&n);
for (int i=;i<=n;++i)
{
scanf("%lf%lf%lf%lf",&a[i].point1.x,&a[i].point1.y,&a[i].point2.x,&a[i].point2.y);
}
if (n==)
{
printf ("Yes!\n");
return ;
}
for (int i=;i<=n;++i)
{
for (int j=i+;j<=n;++j)
{
if (check(a[i].point1,a[j].point1))
{
printf ("Yes!\n");
return ;
}
if (check(a[i].point1,a[j].point2))
{
printf ("Yes!\n");
return ;
}
if (check(a[i].point2,a[j].point1))
{
printf ("Yes!\n");
return ;
}
if (check(a[i].point2,a[j].point2))
{
printf ("Yes!\n");
return ;
}
}
}
printf ("No!\n");
return ;
} int main()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d",&t);
while(t--) work();
return ;
}