51nod1369 无穷印章

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

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

51nod1369 无穷印章
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 ;
}
上一篇:阻止a标签跳转四种方法 兼容各大浏览器(包括IE)


下一篇:DOS批处理命令-for语句