Archaeologists find ruins of Ancient ACM Civilization, and they want to rebuild it. 

The ruins form a closed path on an x-y plane, which has nn endpoints. The endpoints locate on (x1,y1)(x1,y1), (x2,y2)(x2,y2), …,(xn,yn)…,(xn,yn) respectively. Endpoint ii and endpoint i?1i?1are adjacent for 1<i≤n1<i≤n, also endpoint 11 and endpoint nn are adjacent. Distances between any two adjacent endpoints are positive integers. 

To rebuild, they need to build one cylindrical pillar at each endpoint, the radius of the pillar of endpoint ii is riri. All the pillars perpendicular to the x-y plane, and the corresponding endpoint is on the centerline of it. We call two pillars are adjacent if and only if two corresponding endpoints are adjacent. For any two adjacent pillars, one must be tangent externally to another, otherwise it will violate the aesthetics of Ancient ACM Civilization. If two pillars are not adjacent, then there are no constraints, even if they overlap each other. 

Note that riri must not be less than 00 since we cannot build a pillar with negative radius and pillars with zero radius are acceptable since those kind of pillars still exist in their neighbors. 

You are given the coordinates of nn endpoints. Your task is to find r1,r2,…,rnr1,r2,…,rnwhich makes sum of base area of all pillars as minimum as possible. 



For example, if the endpoints are at (0,0)(0,0), (11,0)(11,0), (27,12)(27,12), (5,12)(5,12), we can choose (r1r1, r2r2, r3r3, r4r4)==(3.753.75, 7.257.25, 12.7512.75, 9.259.25). The sum of base area equals to 3.752π+3.752π+7.252π+12.752π+9.252π=988.816…7.252π+12.752π+9.252π=988.816…. Note that we count the area of the overlapping parts multiple times. 

If there are several possible to produce the minimum sum of base area, you may output any of them.

3
4
0 0
11 0
27 12
5 12
5
0 0
7 0
7 3
3 6
0 6
5
0 0
1 0
6 12
3 16
0 12

988.82
3.75
7.25
12.75
9.25
157.08
6.00
1.00
2.00
3.00
0.00
IMPOSSIBLE

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <vector>
 12 #include <stack>
 13 #define mp make_pair
 14 //#define P make_pair
 15 #define MIN(a,b) (a>b?b:a)
 16 //#define MAX(a,b) (a>b?a:b)
 17 typedef long long ll;
 18 typedef unsigned long long ull;
 19 const int MAX=1e4+5;
 20 const int MAX_V=1e3+5;
 21 const ll INF=4e18+5;
 22 const double M=4e18;
 23 using namespace std;
 24 const int MOD=1e9+7;
 25 typedef pair<ll,int> pii;
 26 const double eps=1e-7;
 27 #define rank rankk
 28 int t,n;
 29 double x[MAX],y[MAX],d[MAX],r[MAX],g[MAX];
 30 int findb(double &l,double &r)
 31 {
 32     l=0,r=min(d[0],d[n-1]);
 33     for(int i=0;i<n-1;i++)
 34         if(i&1)
 35             l=max(l,g[i]);
 36         else
 37             r=min(r,g[i]);
 38 }
 39 void solve_odd()
 40 {
 41     double sum=0.0,an=0.0;
 42     for(int i=0;i<n;i++)
 43         if(i&1)
 44             sum-=d[i];
 45         else
 46             sum+=d[i];
 47     r[0]=sum/2.0;
 48     if(r[0]<-eps)
 49     {
 50         printf("IMPOSSIBLE\n");return;
 51     }
 52     else
 53     {
 54         for(int i=0;i<n;i++)
 55         {
 56             an+=r[i]*r[i];
 57             r[i+1]=d[i]-r[i];
 58             if(i+1!=n&&r[i+1]<-eps)
 59             {
 60                 printf("IMPOSSIBLE\n");return;
 61             }
 62         }
 63     }
 64     printf("%.2f\n",an*acos(-1.0));
 65     for(int i=0;i<n;i++)
 66         printf("%.2f\n",r[i]);
 67     return;
 68 }
 69 double get(double m) {
 70     double re=m*m,r=m;
 71     for (int i=0;i<n-1;i++) {
 72         r=d[i]-r;
 73         re+=r*r;
 74     }
 75     return re;
 76 }
 77 
 78 void solve_even()
 79 {
 80     if(abs(g[n-1])>eps)
 81     {
 82         printf("IMPOSSIBLE\n");return;
 83     }
 84     double l,r;
 85     findb(l,r);
 86     if(l>r+eps)
 87     {
 88         printf("IMPOSSIBLE\n");return;
 89     }
 90     while(r-l>eps)
 91     {
 92         double L,R;
 93         L=(2.0*l+r)/3.0;R=(l+2.0*r)/3.0;
 94         if(get(L)>=get(R)+eps)
 95             l=L;
 96         else
 97             r=R;
 98     }
 99     printf("%.2f\n",get(l)*acos(-1.0));
100     for(int i=0;i<n;i++)
101     {
102         printf("%.2f\n",l);
103         l=d[i]-l;
104     }
105 }
106 int main()
107 {
108     scanf("%d",&t);
109     while(t--)
110     {
111         scanf("%d",&n);
112         for(int i=0;i<n;i++)
113         {
114             scanf("%lf%lf",&x[i],&y[i]);
115             if(i)
116                 d[i-1]=sqrt((x[i]-x[i-1])*(x[i]-x[i-1])+(y[i]-y[i-1])*(y[i]-y[i-1]));
117         }
118         d[n-1]=sqrt((x[n-1]-x[0])*(x[n-1]-x[0])+(y[n-1]-y[0])*(y[n-1]-y[0]));
119         g[0]=d[0];
120         for(int i=1;i<n;i++)
121             if(i&1)
122                 g[i]=g[i-1]-d[i];
123             else
124                 g[i]=g[i-1]+d[i];
125         if(n&1)
126             solve_odd();
127         else
128             solve_even();
129     }
130     return 0;
131 }