#include using namespace std; #define REP(i,a,b) for(i=a;i'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(double *x){scanf("%lf",x);} int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;} template void reader(T *x, S *y){reader(x);reader(y);} template void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);} template void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);} void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} void writer(double x, char c){printf("%.15f",x);mypc(c);} void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);} void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);} template void writerLn(T x){writer(x,'\n');} template void writerLn(T x, S y){writer(x,' ');writer(y,'\n');} template void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');} template void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');} void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;} int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;} int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;} char memarr[17000000]; void *mem = memarr; #define MD 1000000007 #define EPS 1e-10 #define PI 3.141592653589793238462 #define MAX(a,b) (((a)>(b))?(a):(b)) #define MIN(a,b) (((a)<(b))?(a):(b)) typedef struct struct_point{double x,y;}pnt; typedef struct struct_line{pnt a,b;}line; typedef struct struct_circle{pnt c; double r;}circle; int doubleSign(double a){if(a>EPS) return 1; if(a<-EPS) return -1; return 0;} int doubleSignR(double a,double b){ if(doubleSign(b)!=0 && doubleSign(a/b-1)==0) return 0; return doubleSign(a-b);} int pntSign(pnt a){int i=doubleSign(a.x); if(i) return i; return doubleSign(a.y);} pnt pntPlus(pnt a,pnt b){a.x+=b.x; a.y+=b.y; return a;} pnt pntMinus(pnt a,pnt b){a.x-=b.x; a.y-=b.y; return a;} pnt pntMultiple(pnt a,pnt b){pnt c; c.x=a.x*b.x-a.y*b.y; c.y=a.x*b.y+a.y*b.x; return c;} pnt pntMultipleDouble(pnt a,double k){a.x*=k; a.y*=k; return a;} int pntIsEqual(pnt a,pnt b){return pntSign(pntMinus(a,b))==0;} double pntLength(pnt a){return sqrt(a.x*a.x+a.y*a.y);} double pntLength2(pnt a){return a.x*a.x+a.y*a.y;} double pntDistance(pnt a,pnt b){return pntLength(pntMinus(a,b));} double pntDistance2(pnt a,pnt b){return pntLength2(pntMinus(a,b));} double pntArgument(pnt a){return atan2(a.y,a.x);} pnt pntNormalize(pnt a){double n=pntLength(a); a.x/=n; a.y/=n; return a;} double pntInnerProduct(pnt a,pnt b){return a.x*b.x+a.y*b.y;} double pntOuterProduct(pnt a,pnt b){return a.x*b.y-a.y*b.x;} pnt pntGenerator(double x,double y){pnt res; res.x=x; res.y=y; return res;} line pntToLine(pnt a,pnt b){line res; res.a=a; res.b=b; return res;} circle pntToCircle(pnt c,double r){circle res; res.c=c; res.r=r; return res;} int isPntInCircle(pnt p,circle c){return doubleSign(c.r-pntDistance(p,c.c))+1;} int isPntOnCircle(pnt p,circle c){if(doubleSign(pntDistance(p,c.c)-c.r)==0) return 1; return 0;} /* aがbの厳密に内部なら2 */ int isCircleInCircle(circle a,circle b){return doubleSign(b.r-a.r-pntDistance(a.c,b.c))+1;} pnt pntPolar(double r,double t){pnt a; a.x=r*cos(t); a.y=r*sin(t); return a;} void pntSort(pnt d[],int s){int i,j;pnt k,t;if(s<=1)return;k=pntMultipleDouble(pntPlus(d[0],d[s-1]),1/2.0);i=-1;j=s;for(;;){while(pntSign(pntMinus(d[++i],k))==-1);while(pntSign(pntMinus(d[--j],k))==1);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}pntSort(d,i);pntSort(d+j+1,s-j-1);} /* 点oのまわりに点aをtだけ回転した点を返す */ pnt pntRatation(pnt a,pnt o,double t){ return pntPlus(pntMultiple(pntMinus(a,o),pntPolar(1.0,t)),o); } pnt pntRatationEasy(pnt a,double t){ return pntMultiple(a,pntPolar(1.0,t)); } /* 直線の上に載っていると1, 載ってなければ0 */ int isPntOnLine(pnt a,line s){ pnt ab; double r; ab=pntMinus(s.b,s.a); r=pntDistance(s.a,a)/pntDistance(s.a,s.b); if( !pntIsEqual(a,pntPlus(s.a,pntMultipleDouble(ab,r)) ) && !pntIsEqual(a,pntMinus(s.a,pntMultipleDouble(ab,r)) ) ) return 0; return 1; } /* 線分の上に載っていると2, 端点なら1, 載ってなければ0 */ int isPntOnSegment(pnt a,line s){ pnt ab; double r; ab=pntMinus(s.b,s.a); r=pntDistance(s.a,a)/pntDistance(s.a,s.b); if( !pntIsEqual(a,pntPlus(s.a,pntMultipleDouble(ab,r)) ) ) return 0; if( doubleSign(r)==-1 || doubleSign(r-1)==1 ) return 0; if( doubleSign(r)==0 || doubleSign(r-1)==0 ) return 1; return 2; } /* 角度bacを返す */ double angleOfTriangle(pnt a,pnt b,pnt c){ double inner,n1,n2; inner=pntInnerProduct(pntMinus(b,a),pntMinus(c,a)); n1=pntDistance(a,b); n2=pntDistance(a,c); inner=inner/n1/n2; if(inner>1) inner=1; if(inner<-1) inner=-1; return acos(inner); } /* 原点中心半径rの円に,pから接線を引いて,接線と円の交点を2つ求める */ /* 制約: pは円の外 */ void pntPointToCircleTangentialEasy(pnt p,double r,pnt *res1,pnt *res2){ double a,b,c,d; if( doubleSign(p.x)==0 ){ a=p.x; p.x=p.y; p.y=a; pntPointToCircleTangentialEasy(p,r,res1,res2); a=res1->x; res1->x=res1->y; res1->y=a; a=res2->x; res2->x=res2->y; res2->y=a; return; } a = pntLength2(p); b = -2*r*r*p.y; c = r*r*(r*r-p.x*p.x); d = sqrt(b*b-4*a*c); res1->y = (-b+d)/(2*a); res2->y = (-b-d)/(2*a); res1->x = (r*r-res1->y*p.y)/p.x; res2->x = (r*r-res2->y*p.y)/p.x; } /* 円cに,pから接線を引いて,接線と円の交点を2つ求める */ /* 制約: pは円の外 */ void pntPointToCircleTangential(pnt p,circle c,pnt *res1,pnt *res2){ pntPointToCircleTangentialEasy( pntMinus(p,c.c), c.r, res1, res2 ); *res1 = pntPlus(*res1,c.c); *res2 = pntPlus(*res2,c.c); } /* 点p から 直線t へ引いた垂線の足を返す */ pnt pntPointLinePerpendicular(pnt p,line t){ double k; pnt ab,ap; ab=pntMinus(t.b, t.a); ap=pntMinus(p, t.a); k=pntInnerProduct(ab,ap)/pntLength2(ab); return pntPlus( t.a, pntMultipleDouble(ab,k) ); } /* 点p の 直線t に対して対称な点を求める */ pnt pntSymmetricPointWithLine(pnt p,line t){ pnt go = pntPointLinePerpendicular(p,t); go=pntMinus(go,p); return pntPlus( p,pntMultipleDouble(go,2) ); } double distancePntSegment(pnt p,line t){ double d1,d2; pnt c = pntPointLinePerpendicular(p,t); if( isPntOnSegment(c,t) ) return pntDistance(p,c); d1 = pntDistance(p,t.a); d2 = pntDistance(p,t.b); if(d1 > d2) return d2; return d1; } double distancePntLine(pnt p,line t){ return pntDistance(p,pntPointLinePerpendicular(p,t)); } /* 速度vで動く点が直線に辿り着くまでの時間 (マイナスもあり) */ /* 戻り値 0=辿り着かない, 1=辿り着く, 2=恒にその直線上を動く */ /* return 1; のとき double res = 辿り着く時間 pnt reachPoint = 辿り着いた場所 */ int getTimeMovingPntReachLine(pnt p,pnt v,line s,double *res, pnt *reachPoint){ pnt lineVector = pntNormalize(pntMinus(s.b,s.a)); double inner = pntInnerProduct(lineVector,v); double dist = distancePntLine(p,s); pnt vv = pntMinus(v,pntMultipleDouble(lineVector,inner)); if(pntSign(vv)==0){ if(doubleSign(dist)==0) return 2; return 0; } *res = dist / pntLength(vv); *reachPoint = pntPlus(p,pntMultipleDouble(v,*res)); if( !isPntOnLine(*reachPoint, s) ){ (*res) *= -1; *reachPoint = pntPlus(p,pntMultipleDouble(v,*res)); } return 1; } /* 長さap : bp = s : tを満たす点pの集合(円)を返す 制約: s!=t */ circle pntSetDivisionPoint(pnt a,double s,pnt b,double t){ pnt r1,r2,ab; circle res; ab=pntMinus(b,a); r1 = pntPlus(a,pntMultipleDouble(ab,s/(s+t))); r2 = pntPlus(a,pntMultipleDouble(ab,s/(s-t))); res.c = pntMultipleDouble(pntPlus(r1,r2),0.5); res.r=pntDistance(r1,r2)/2; return res; } /* a x^2 + b x + c = 0 を解く.戻り値は解の数.解の数が2ならres1 < res2. */ /* 解の数が無限なら return 3; */ int doubleSolveSecondDegreeEquation(double a,double b,double c,double *res1,double *res2){ if(doubleSign(a)){ double d=b*b-4*a*c; int m=doubleSign(d)+1; if(m==1) *res1=-b/(2*a); if(m==2){d=sqrt(d); *res1=(-b-d)/(2*a); *res2=(-b+d)/(2*a);} return m; } if(doubleSign(b)){*res1 = -b/c; return 1;} if(doubleSign(c)) return 0; return 3; } /* 直線 t と円 s の交点を求める.戻り値は交点の数.(3次元での球-直線の交点とほぼ同じコード) */ /* 2点で交わるなら,res1はt.aに近い側,res2はt.bに近い側 */ int pntIntersectionLineCircle(line t,circle s,pnt *res1,pnt *res2){ int m; double a,b,c,t1,t2,k1,k2; pnt ab=pntMinus(t.b, t.a); a=b=0; c=-s.r*s.r; t1=t.a.x-s.c.x; t2=t.b.x-t.a.x; a+=t2*t2; b+=2*t1*t2; c+=t1*t1; t1=t.a.y-s.c.y; t2=t.b.y-t.a.y; a+=t2*t2; b+=2*t1*t2; c+=t1*t1; m=doubleSolveSecondDegreeEquation(a,b,c,&k1,&k2); if(m>=1) *res1 = pntPlus( t.a, pntMultipleDouble(ab,k1) ); if(m>=2) *res2 = pntPlus( t.a, pntMultipleDouble(ab,k2) ); return m; } /* 線分 t (端は含む) と円 s の交点を求める.戻り値は交点の数.(3次元での球-直線の交点とほぼ同じコード) */ /* 2点で交わるなら,res1はt.aに近い側,res2はt.bに近い側 */ int pntIntersectionSegmentCircle(line t,circle s,pnt *res1,pnt *res2){ int m; double a,b,c,t1,t2,k1,k2; pnt ab=pntMinus(t.b, t.a); a=b=0; c=-s.r*s.r; t1=t.a.x-s.c.x; t2=t.b.x-t.a.x; a+=t2*t2; b+=2*t1*t2; c+=t1*t1; t1=t.a.y-s.c.y; t2=t.b.y-t.a.y; a+=t2*t2; b+=2*t1*t2; c+=t1*t1; m=doubleSolveSecondDegreeEquation(a,b,c,&k1,&k2); if(m>=2) if(doubleSign(k2)==-1 || doubleSign(k2-1)==1) m--; if(m>=1) if(doubleSign(k1)==-1 || doubleSign(k1-1)==1) k1=k2, m--; if(m>=1) *res1 = pntPlus( t.a, pntMultipleDouble(ab,k1) ); if(m>=2) *res2 = pntPlus( t.a, pntMultipleDouble(ab,k2) ); return m; } /* ax + by + c = 0 を表す直線を返す (制約: a=b=0ではない) */ line pntGetLineFromCoefficient(double a,double b,double c){ line res; if( doubleSign(a)==0 ){ res.a.x = 0; res.b.x = 1; res.a.y = res.b.y = -c/b; } else { res.a.y=0; res.b.y=1; res.a.x=-c/a; res.b.x=(-b-c)/a; } return res; } /* 2つの円の交点を求める.戻り値の値は交点の数.戻り値が3ならば無限点で交わる */ int pntIntersectionCircleCircle(circle s1,circle s2,pnt *res1,pnt *res2){ double a,b,c; line t; double x1=s1.c.x, x2=s2.c.x, y1=s1.c.y, y2=s2.c.y, r1=s1.r, r2=s2.r; if( pntIsEqual(s1.c,s2.c) ){ if( doubleSign(s1.r-s2.r)==0 ) return 3; return 0; } a = 2*(x1-x2); b = 2*(y1-y2); c = (x2*x2-x1*x1) + (y2*y2-y1*y1) - (r2*r2-r1*r1); t = pntGetLineFromCoefficient(a,b,c); return pntIntersectionLineCircle(t,s1,res1,res2); } /* 三角形の符号付面積の2倍 */ double pntAreaOfTriangle2(pnt p1,pnt p2,pnt p3){ double x1,x2,y1,y2; x1=p2.x-p1.x; x2=p3.x-p1.x; y1=p2.y-p1.y; y2=p3.y-p1.y; return x1*y2-x2*y1; } /* 符号付面積の符号を返す */ /* p1,p2の直線の左にp3がある場合,戻り値=1 */ /* p1,p2の直線の右にp3がある場合,戻り値=-1 */ /* p1,p2,p3が一直線上にある場合, 戻り値=0 */ int pntSignAreaOfTriangle(pnt p1,pnt p2,pnt p3){ return doubleSign( pntAreaOfTriangle2(p1,p2,p3) ); } /* 2直線の交点を求める (交わる点が無限大の場合の判定は未実装) */ /* 戻り値: 交点の数 無限大の場合も0を返す */ /* 後の仕様予定: return 2が無限大の場合 */ int pntIntersectionLineLine(line s,line t,pnt *res){ pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b; double r = (p4.y-p3.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p4.x-p3.x); if( doubleSign(r)==0 ) return 0; res->x = (p3.x*p4.y-p3.y*p4.x)*(p2.x-p1.x)-(p1.x*p2.y-p1.y*p2.x)*(p4.x-p3.x); res->y = (p3.y*p4.x-p3.x*p4.y)*(p2.y-p1.y)-(p1.y*p2.x-p1.x*p2.y)*(p4.y-p3.y); res->x /= r; res->y /= -r; return 1; } /* s=line, t=segment */ int pntIntersectionLineSegment(line s,line t,pnt *res){ pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b; if(pntSignAreaOfTriangle(s.a, s.b, t.a)==0 || pntSignAreaOfTriangle(s.a, s.b, t.b)==0){ return 1; } double x1,x2,y1,y2; if(pntIntersectionLineLine(s,t,res)!=1) return 0; x1=MIN(p3.x,p4.x)-EPS; x2=MAX(p3.x,p4.x)+EPS; y1=MIN(p3.y,p4.y)-EPS; y2=MAX(p3.y,p4.y)+EPS; if(res->x < x1 || x2 < res->x || res->y < y1 || y2 < res->y) return 0; if(pntIsEqual(*res,p3)) return 1; if(pntIsEqual(*res,p4)) return 1; return 2; } int N; line p[100], s; pnt ptmp; int main(){ int i, j, k; int res, tmp; reader(&N); rep(i,N) reader(&p[i].a.x, &p[i].a.y, &p[i].b.x, &p[i].b.y); res = min(2, N); rep(i,2*N) rep(j,2*N){ tmp = 0; if(i