#include #include #include #include #define REP(i,a,b) for(i=a;i=0;k--)if(d[k]d[k])break;j=d[i],d[i]=d[k],d[k]=j;intReverse(d+k+1,size-k-1);return 1;} int outer(int x1, int y1, int x2, int y2){ return x1*y2 - x2*y1; } /* return 1 if and only if two segments (x1,y1)-(x2,y2), (x3,y3)-(x4,y4) have an intersection */ int iscross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){ int o1, o2; o1 = outer(x2-x1, y2-y1, x3-x1, y3-y1); o2 = outer(x2-x1, y2-y1, x4-x1, y4-y1); if( (o1 < 0 && o2 > 0) || (o1 > 0 && o2 < 0) ) return 0; o1 = outer(x4-x3, y4-y3, x1-x3, y1-y3); o2 = outer(x4-x3, y4-y3, x2-x3, y2-y3); if( (o1 < 0 && o2 > 0) || (o1 > 0 && o2 < 0) ) return 0; return 1; } int dist2(int dx, int dy){ return dx*dx + dy*dy; } int main(){ int i,j,k; int T, N, X[1000], Y[1000], sumN = 0; int d[4]; int res; assert( scanf("%d",&T)==1 ); assert( 1<=T && T<=1250 ); while(T--){ assert( scanf("%d",&N)==1 ); sumN += N; assert( 4<=N && N<=1000 && sumN<=5000 ); rep(i,N) assert( scanf("%d%d",X+i,Y+i)==2 ), assert(1<=X[i]&&X[i]<=5000 && 1<=Y[i]&&Y[i]<=5000); if(0){ /* it is not a part of solution (just check that input is correct) */ rep(i,N) REP(j,i+1,N) REP(k,j+1,N) assert( outer(X[j]-X[i], Y[j]-Y[i], X[k]-X[i], Y[k]-Y[i]) != 0 ); } res = 0; if(N==4){ rep(i,N) d[i] = i; do{ /* btute-force (check every tetragons = every permutations of points) */ if( iscross(X[d[0]], Y[d[0]], X[d[2]], Y[d[2]], X[d[1]], Y[d[1]], X[d[3]], Y[d[3]]) ) continue; rep(i,4){ k = dist2(X[d[i]]-X[d[(i+1)%4]], Y[d[i]]-Y[d[(i+1)%4]]); if(res < k) res = k; } }while(intNextPermutation(d+1,N-1)); /* intNextPermutation is the same as next_permutation(d+1, d+N) in C++ */ } else { /* N >= 5 */ rep(i,N) REP(j,i+1,N){ k = dist2(X[i]-X[j], Y[i]-Y[j]); if(res < k) res = k; } } printf("%.10f\n", sqrt(res)); } return 0; }