51nod1369 无穷印章

有一个印章，其完全由线段构成。这些线段的线足够细可以忽略其宽度，就像数学上对线的定义一样，它们没有面积。现在给你一张巨大的白纸（10亿x10亿大小的纸，虽然这个纸很大，但是它的面积毕竟还是有限的），你可以在上面盖这个印章。要求盖印章时只能平移印章不能将其旋转，同时两次印章盖下的痕迹不能有交点（存在交点，指的是两次盖完印章后，可以从第一次的印章图案中取出一条线段，同时第二次的图案中也取出一条线段，且这两天线段相交）。给定印章中的图案，请判断是否有办法在这个有限的白纸上盖无限个章？存在输出"Infinite",否则输出"Finite".

提示：下图给出一些印章图案以及它们对应的结果。

Input

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5

每组测试数据有相同的结构构成。

每组数据的第一行包含一个整数N，表示印章中的线段条数，其中1<=N<=50

接下来N行每行四个整数ai,bi,ci,di，表示一条线段的两个端点(ai,bi)与(ci,di)，其中-1000<=ai,bi,ci,di<=1000

Output

每组数据一行输出，存在无穷个印章的盖法输出"Infinite",否则输出"Finite".

这题卡精度。。。最好不要用浮点数。。。

答案为Infinite当且仅当存在一个方向，使印章在此方向平移一个极小（趋向于0）的距离后不与自身相交，而每对仅在端点相交的线段就确定了两个方向区间，不能向区间内方向平移，离散化，排序扫一次就可以确定是否有满足要求的方向存在

#include<cstdio>

#include<algorithm>

struct vec{

    int x,y;

    void fix(){

        if(y<||y==&&x<)x=-x,y=-y;

    }

};

vec operator+(vec a,vec b){return (vec){a.x+b.x,a.y+b.y};}

vec operator-(vec a,vec b){return (vec){a.x-b.x,a.y-b.y};}

int operator*(vec a,vec b){return a.x*b.y-a.y*b.x;}

bool operator==(vec a,vec b){return a.x==b.x&&a.y==b.y;}

struct seg{

    vec a,b;

    void scan(){

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

    }

    void swap(){

        std::swap(a,b);

    }

    bool isp(){

        vec c=a-b;

        return !(c.x|c.y);

    }

}ss[];

int ep,sum,cnt;

int sgn(int x){

    return x>?:x<?-:;

}

bool cross(seg a,seg b){

    return

    sgn((b.a-a.a)*(a.b-a.a))*sgn((b.b-a.a)*(a.b-a.a))+

    sgn((a.a-b.a)*(b.b-b.a))*sgn((a.b-b.a)*(b.b-b.a))<;

}

bool pal(seg a,seg b){

    return (a.b-a.a)*(b.b-b.a)==;

}

struct event{

    vec x;int v;

}es[];

bool operator<(event a,event b){

    int c=a.x*b.x;

    return c?c>:a.v<b.v;

}

void chk(seg a,seg b){

    if(a.a==b.b)b.swap();

    if(a.b==b.a)a.swap();

    if(a.b==b.b)a.swap(),b.swap();

    if(a.a==b.a){

        vec p1=a.b-a.a,p2=b.b-b.a;

        if(p1*p2<)std::swap(p1,p2);

        p1.fix();p2.fix();

        if(p1*p2<)++sum;

        ++cnt;

        es[ep++]=(event){p1,};

        es[ep++]=(event){p2,-};

    }

}

int T,n;

int main(){

    scanf("%d",&T);

    while(T--){

        ep=;sum=cnt=;

        scanf("%d",&n);

        for(int i=;i<n;i++)ss[i].scan();

        int is=;

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

            if(ss[i].isp()||ss[j].isp())continue;

            if(pal(ss[i],ss[j]))continue;

            if(cross(ss[i],ss[j])){

                is=;

                i=n;

                break;

            }

            chk(ss[i],ss[j]);

        }

        if(is){

            std::sort(es,es+ep);

            for(int i=;i<ep;i++){

                if((sum+=es[i].v)==cnt){

                    is=;

                    break;

                }

            }

        }

        puts((is==||is==&&!cnt)?"Infinite":"Finite");

    }

    return ;

}