题意:给出n条线段,求是否有一条直线能够与全部线段相交.

由于一条穿过所有的线段的直线,总可以通过平移来使得其通过某两个端点,故枚举端点,判断过端点的直线是否能穿过所有线段即可.

此题WA几次..究其原因为: 叉积之前需要判断给出的向量是否为0,为0则不能进行叉积操作..

刚刚开始做计算几何…orz各路神犇..希望能够快快长进!

# include <iostream>
# include <cmath>
# define sqr(x) ((x)*(x))
# define rep(x, n) for (int x = 0; x < n; ++x )
using namespace std;

const double eps = 1e-8;
int dcmp(double x){ return (x > eps) - (x < -eps);}

class Point
{
    public:
    double x, y;
    Point(){x = y = 0.0;}
    Point(double a, double b){ x = a; y = b; }

    inline Point operator -(const Point& b)
    { return Point(x-b.x, y-b.y);}

    inline double cross(const Point& b, const Point& c)
    { return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y); }

    inline double dis(const Point& b)
    { return sqrt( sqr(b.x - x) + sqr(b.y - y) ); }

}line[103][2];

int t, n;
bool ok;

void check(Point& a, Point& b)
{
    if ( dcmp(a.dis(b)) == 0 ) return;
    rep(i, n)
        if ( dcmp(a.cross(b, line[i][0]) * a.cross(b, line[i][1])) > 0 )
            return;
    ok = true;
    return;
}
int main()
{
    double x, y;
    cin >>t;
    while( t-- )
    {
        cin >>n;
        rep(i, n)
        {
            cin >> x >> y;
            line[i][0] = Point(x, y);
            cin >> x >> y;
            line[i][1] = Point(x, y);
        }
        ok = false;
        rep(i, n)
            for (int j = i+1; j < n; ++j )
            {
                if ( ok ) break;
                check(line[i][0], line[j][0]);
                check(line[i][0], line[j][1]);
                check(line[i][1], line[j][0]);
                check(line[i][1], line[j][1]);
            }
        if ( n == 1 ) ok = true;
        if ( ok ) cout << "Yes!" <<endl;
        else cout << "No!" << endl;
    }
    return 0;
}