poj 3304 Segments

poj 3304 Segments （计算几何水题）

链接：http://poj.org/problem?id=3304

题意：找出一条直线，使得给出的所有线段在这个直线上的投影有交集。

思路：找出一条直线，使得其与所给的线段有交点。枚举每一个线段的端点，假设直线经过某两点，判断直线是否与其它线段相交。枚举这些点的位置即可。主意其中的输出大小写，我wa了一个晚上就是输出的大小写写错了，无语（小小吐槽一番）！

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const int N = 210;
inline int sig(double x) { return (x>eps)-(x<-eps);}

struct P{
    double x, y;
    inline void in(){ scanf("%lf%lf", &x, &y); }
    inline bool operator == (const P a){    //同一个点
        if(sig(x-a.x) == 0 && sig(y-a.y) == 0)    return true;
        return false;
    }
    inline double cross(P a, P b) const {    //叉积
        return (x-b.x)*(a.y-b.y) - (a.x-b.x)*(y-b.y);
    }
} p[N];

int t, n;

int main()
{
    int i, j, k;
    //freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        n += n;
        for(i = 0; i < n; i++) p[i].in();
        bool fg = 0;
        for(i = 0; i < n && !fg; i++)
            for( j = 0; j < n; j++)
            {
                if(p[i] == p[j])    continue;
                for(k = 0; k < n; k += 2)
                    if(p[k].cross(p[i], p[j]) * p[k+1].cross(p[i], p[j]) > eps)    // 不相交，不符合
                        break;
                if(k >= n)    fg = 1;
            }
        puts((fg) ? "Yes!" : "No!");
    }
    return 0;
}