//OUM HARI OUM, OUM TATSAT // OUM NAMA VAGABATE BASUDEBAY // OUM NAMA MA SWARASATI OUM NAMA #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define sc1(a) scanf("%d",&a) #define sc2(a,b) scanf("%d %d",&a,&b) #define sc3(a,b,c) scanf("%d %d %d",&a,&b,&c) #define scd1(a) scanf("%lf",&a) #define scd2(a,b) scanf("%lf %lf",&a,&b) #define scd3(a,b,c) scanf("%lf %lf %lf",&a,&b,&c) #define scl1(a) scanf("%lld",&a) #define scl2(a,b) scanf("%lld %lld",&a,&b) #define scl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define cl(vctr) vctr.clear() #define ms(v, ar) memset(ar, v, sizeof(ar)) const double pi=(double)(2.0 * acos( 0.0 )); const int inf=1 << 30; const double eps=1E-9; const double e = exp(1.0); const int sz=100000 + 5; using namespace std; typedef long long int ll; const ll mod=1000000000 + 7; struct pt{double x, y;}; struct VC{ double x,y; VC(double x = 0, double y = 0){ this-> x = x; this-> y = y;} }; VC VB(VC a, VC b){ return VC( b.x - a.x, b.y - a.y ); } VC VADD(VC a, VC b){ return VC( b.x + a.x, b.y + a.y ); } double VM(VC a){ return sqrt( a.x * a.x + a.y * a.y); } double SCP(VC a, VC b){ return (a.x * b.x + a.y * b.y); } double VCP(VC a, VC b){ double M = a.x * b.y - b.x * a.y; return M; } bool cmp(VC a,VC b) { return ((a.x createHull(vector A){ int nn=A.size(),k=0,i,t; vector H(2*nn); sort(A.begin(),A.end(),cmp); for(i=0;i=2&&VCP(VB(H[k-1],H[k-2]),VB(H[k-1],A[i]))>eps)) k--; H[k++]=A[i]; } for(i=nn-2,t=k+1;i>=0;i--){ while((k>=t&&VCP(VB(H[k-1],H[k-2]),VB(H[k-1],A[i]))>eps)) k--; H[k++]=A[i]; } k--; H.resize(k); return H; } VC rot(VC a,double ang) { double x=a.x*cos(ang)-a.y*sin(ang); double y=a.x*sin(ang)+a.y*cos(ang); return VC(x,y); } int vis[11],col[11]; int main() { ll t; scl1(t); while(t--) { ll n; double x,y; scl1(n); vector A; for(ll i=0;iA[i].y) mny=A[i].y,a=i; if(mxxA[i].x) mnx=A[i].x,d=i; } VC a1=VB(A[a],VC(10005,A[a].y)); VC b1=VB(A[b],VC(A[b].x,10005)); VC c1=VB(A[c],VC(-10005,A[c].y)); VC d1=VB(A[d],VC(A[d].x,-10005)); ms(0,col); bool ch=0; while(!ch) { if(col[a]==4 || col[b]==4 || col[c]==4 ||col[d]==4) break; ms(0,vis); for(ll i=0;iang1) ang=ang1,idx=a; tmp=VB(A[b],A[(b+1)%n]); double ang2=acos(1.0*SCP(tmp,b1)/VM(tmp)/VM(b1)); if(ang>ang2) ang=ang2,idx=b; tmp=VB(A[c],A[(c+1)%n]); double ang3=acos(1.0*SCP(tmp,c1)/VM(tmp)/VM(c1)); if(ang>ang3) ang=ang3,idx=c; tmp=VB(A[d],A[(d+1)%n]); double ang4=acos(1.0*SCP(tmp,d1)/VM(tmp)/VM(d1)); if(ang>ang4) ang=ang4,idx=d; a1=VADD(A[a],rot(a1,ang)); b1=VADD(A[b],rot(b1,ang)); c1=VADD(A[c],rot(c1,ang)); d1=VADD(A[d],rot(d1,ang)); if(fabs(ang-ang1)