#include bool squareCrossAndInCheck(int xs1[4],int ys1[4],int xs2[4],int ys[4]);//四角形と四角形が交点、もしくは接する、内部にあるならtrueを返す bool inTriangle(int x1,int x2,int x3,int x4,int y1,int y2,int y3,int y4);//四角形を三角形に分割して三角形内部に点があるなら四角形内部に他の四角形の点がある bool cross(int x1,int x2,int x3,int x4,int y1,int y2,int y3,int y4);//四角形を構成する線分と線分が交点を持つかをチェックする int pointHerf(int x1,int x2,int x3,int y1,int y2,int y3);//辺と辺が平行な時、辺が共有部分を持つかをチェックする int lineHerf(int x1,int x2,int x3,int y1,int y2,int y3);//平面を直線で区切った時 void setMap(int n);//四角形のイルミネーションデータのセット void saiki(int pointer,int m);//つながっている四角形をたどっていく関数 bool g[101][101];//四角形のつながりをあらわすグラフ int moveOK[101];//四角形がまだどの四角形に分類されてないならtrueに設定されている int main() { int n,m; scanf("%d",&n); while(n!=0){ setMap(n); scanf("%d",&n); } } void setMap(int n){ int count=1; int m; int xs[101][4];//一つのイルミネーションを構成する四角形のx座標 int ys[101][4];//y座標 bool isSquareUnion; for(int i=0;i=0;j--){ for(int k=0;k<=j;k++){ if(j==k){ g[j][j]=0; continue; } isSquareUnion=squareCrossAndInCheck(xs[j],ys[j],xs[k],ys[k]); if(isSquareUnion==true){ g[j][k]=g[k][j]=1;//k番目の四角形とj番目の四角形は共有部分を持っていた }else{ g[j][k]=g[k][j]=0;//共有部分を持っていなかった } } } int count=0; for(int j=0;j0) return false; t3=lineHerf(x3,x4,x1,y3,y4,y1); t4=lineHerf(x3,x4,x2,y3,y4,y2); if(t3*t4>0) return false; //線分が交点を持つ if(t1*t2<0 && t3*t4<0) return true; //片方の線分の点がもう片方の線分の上にある if((t1*t2==0 && t3*t4<0) || (t1*t2<0 && t3*t4==0)) return true; if(t1*t2==0 && t3*t4==0){ //両片が平行な場合 //線分上の端点からみて両側にもう片方の線分の点があるか t1=pointHerf(x1,x2,x3,y1,y2,y3); t2=pointHerf(x1,x2,x4,y1,y2,y4); if(t1*t2<0) return true; t1=pointHerf(x2,x1,x3,y2,y1,y3); t2=pointHerf(x2,x1,x4,y2,y1,y4); if(t1*t2<0) return true; t1=pointHerf(x3,x4,x1,y3,y4,y1); t2=pointHerf(x3,x4,x2,y3,y4,y2); if(t1*t2<0) return true; t1=pointHerf(x4,x3,x1,y4,y3,y1); t2=pointHerf(x4,x3,x2,y4,y3,y2); if(t1*t2<0) return true; } //点を共有せず、交点も持たず、片方の線分上に片方の線分がないかつ線分が平行で重なることもない場合 return false; } int pointHerf(int x1,int x2,int x3,int y1,int y2,int y3){ //2つの線分が並行で同一直線状にある時、線分の点のどちら側にもう片方の線分の点があるかをチェックする関数 return (x2-x1)*(x3-x1)+(y2-y1)*(y3-y1); } int lineHerf(int x1,int x2,int x3,int y1,int y2,int y3){ //直線で切り分けた時の半開平面のどちら側に点があるか return (y2-y1)*(x3-x1)+y1*(x2-x1)+(x1-x2)*y3; }