Sana In The Forest

//OM
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <sstream>
#include <algorithm>
using  namespace  std;

#define  x first
#define  y second
#define  pb push_back
#define  mp make_pair
#define  PI (acos(-1.0))
#define  mem(a,b) memset(a,b,sizeof(a))
#define  Sort(x) sort(x.begin(),x.end())
#define  FOR(i, b, e) for(int i = b; i <= e; i++)
#define  FORR(i, b, e) for(int i = b; i >= e; i--)
#define  FORI(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define  pr(x) cout<<x<<"\n"
#define  prs(x) cout<<x<<" "
#define  pr2(x,y) cout<<x<<" "<<y<<"\n"
#define  pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define  ppr(a) cout<<a.x<<" "<<a.y<<"\n"

typedef  long long ll;
typedef  pair <ll, ll> pii;
typedef  pair <double , double> pdd;
typedef  vector <int> vi;
typedef  vector <pii> vpii;

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};
//int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction

#define  EPS 1e-9
#define  MAX 1000007
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

/*
Problem: Sana in the forest
Level: Easy Medium
Author: Abinash Ghosh
Algorithm/Technique: Convex Hull
Complexity: O(n log n)
Analysis:
    Basic Computational geometry problem. For minimize the length of fence , you have to construct
    a convex polygon covering all the trees and perimeter of the polyon is the required value.
*/

pair<int , int > p0,pnt[MAX],res[MAX];
inline ll cross(pii a, pii b, pii c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void Convex_Hull(int np,int &nc)
{
    sort(pnt,pnt+np);
    int j=0;
    //use <= to remove colinear points
    FOR(i,0,np-1){
        while(j>=2&&cross(res[j-2],res[j-1],pnt[i])<=0)j--;
        res[j++]=pnt[i];
    }
    for(int i=np-2,t=j+1; i>=0; i--){
        while(j>=t&&cross(res[j-2],res[j-1],pnt[i])<=0)j--;
        res[j++]=pnt[i];
    }
    nc=j-1;
}
double pPerimeter(int n)
{
    double result=0,dx,dy;
    for(int i=0;i<n;++i)
    {
        dx= res[(i+1)%n].x - res[i].x;
        dy= res[(i+1)%n].y - res[i].y;
        result+=sqrt(dx*dx+dy*dy);
    }
    return result;
}
int main()
{
    //READ("in.txt");
    //WRITE("out.txt");
    int T;
    scanf("%d",&T);
    FOR(cs,1,T)
    {
        int point,Bpoint;
        scanf("%d",&point);
        FOR(i,0,point-1)
        scanf("%d %d",&pnt[i].x,&pnt[i].y);
        Convex_Hull(point,Bpoint);
        double ans=pPerimeter(Bpoint);
        printf("%.6lf\n",ans);
    }
    return 0;
}