Segments poj 3304 计算几何

题意

给出n条线段，判断是否存在有一条直线，满足所有的线段在直线上投影后至少有一个公共点

分析

原命题等价为存在一条直线穿过所有的线段
（易知过公共点且垂直于所求直线的直线符合条件，设为直线a），
该命题又等价于从所有线段中任选两端点形成的直线存在可以穿过所有的线段的直线（可将a平移至一条线段端点，然后绕这点旋转，使a过另一条线段端点），
所以我们直接枚举两个端点，用叉积判断其他的线段是否被穿过。水~~

ps：要不是poj的pascal编译器出毒，我才不用c++呢，c++的数组是从0开始的。

代码

#include<iostream> 
#include<cstdio>
#include<cmath>

using namespace std;

const double eps=1e-10;
double x[201],y[201];
int n,m;
int init()
{
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
        scanf("%lf%lf%lf%lf",&x[i*2-1],&y[i*2-1],&x[i*2],&y[i*2]);
    m=m*2;
    return 0;
} 

void add()
{
    for (int i=1;i<=m;i++)
      for (int j=i+1;j<=m;j++)
        {
            if ((abs(x[i]-x[j])<eps)&&(abs(y[i]-y[j])<eps))
              {
                continue;
              }
            bool flag=true;
            int k=1;
            while (k<=m)
              {
                double r1,r2;
                r1=(x[i]-x[j])*(y[k]-y[j])-(x[k]-x[j])*(y[i]-y[j]);
                k+=1;
                r2=(x[i]-x[j])*(y[k]-y[j])-(x[k]-x[j])*(y[i]-y[j]);
                k+=1;
                if (r1*r2>0)
                  {
                    flag=false;
                    break;
                  }
              }
            if (flag)
              {
                printf("Yes!\n");
                return;
              }
        }
    printf("No!\n");
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
      {
        init();
        add();
      }
    return 0;

}