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.

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x₁ y₁ x₂ y₂ follow, in which (x₁, y₁) and (x₂, y₂) are the coordinates of the two endpoints for one of the segments.

For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10^-8.

#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

struct Point{

    double x,y;

    Point(){}

    Point(double x,double y):x(x),y(y){}

};

struct Segment{

    Point a,b;

};

typedef Point Vector;

Vector operator -(const Point &A,const Point &B){ return Vector(A.x-B.x,A.y-B.y);}

bool operator < (const Point &a,const Point &b)

{

    return a.x<b.x||(a.x==b.x&&a.y<b.y);

}

const double eps=1e-;

int dcmp(double x)

{

    if(fabs(x)<eps) return ;

    else return x<?-:;

}

bool operator == (const Point &a,const Point &b){

    return (dcmp(a.x-b.x)== && dcmp(a.y-b.y)==);

}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//点积

double Length(Vector A){return sqrt(Dot(A,A));}//向量长度

//两向量的夹角

double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}

double Cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x;}//叉积

vector<Segment> S;

bool judge(Point a,Point b)

{

    if(a == b) return false;//a,b属于同一个点，一个点不能确定一条直线

    int i,n=S.size();

    Vector v1=b-a,v2,v3;

    for(i=;i<n;i++)

    {

        v2=S[i].a-a;

        v3=S[i].b-a;

        if(dcmp(Cross(v1,v2)*Cross(v1,v3)) > ) return false;

    }

    return true;

}

bool solve()

{

    int i,j,n=S.size();

    for(i=;i<n;i++)

    {

        for(j=i+;j<n;j++)

        if(judge(S[i].a,S[j].a) || judge(S[i].a,S[j].b) || judge(S[i].b,S[j].a) || judge(S[i].b,S[j].b))

              return true;

    }

    return false;

}

int main()

{

    int T,n,i;

    Segment s;

    scanf("%d",&T);

    while(T--)

    {

        S.clear();

        scanf("%d",&n);

        for(i=;i<n;i++)

        {

            scanf("%lf %lf %lf %lf",&s.a.x,&s.a.y,&s.b.x,&s.b.y);

            S.push_back(s);

        }

        if(n==) printf("Yes!\n");

        else if(solve()) printf("Yes!\n");

        else printf("No!\n");

    }

    return ;

}