Given a set of N integer points on the Cartesian plane. Your task is to find an integer point satisfying its sum of distances to N given points (S) is minimum.

Input

There are several test cases (fifteen at most), each formed as follows:

  • The first line contains a positive integer N (N ≤ 2,000).
  • N lines follow, each containing a pair of integers (each having an absolute value of 109 at most) describing coordinates of a given point.

The input is ended with N = 0.

Output

For each test case, output on a line a real number (with exactly 6 decimal places) which is the respective minimum sum S found.

Example

Input:
3
1 1
2 2
3 3
5
1 4
2 3
5 2
3 5
4 1
0

Output:
2.828427
9.640986

Solution:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)

const int maxn=2000+5;

int n;
int x[maxn],y[maxn];
int minx,maxx,miny,maxy;
double result;

double calc(double x0,double y0)
{
double s=0;
for (int i=0;i<n;i++) s+=sqrt(sqr(x0-x[i])+sqr(y0-y[i]));
if (s<result) result=s;
return s;
}
double calc_byx(int x0)
{
int sy=miny,ty=maxy;
double R=1e100;
for (;ty-sy>10;)
{
int y1=sy+(ty-sy)/3;
int y2=ty+(sy-ty)/3;
double v1=calc(x0,y1);
double v2=calc(x0,y2);
if (v1<R) R=v1;
if (v2<R) R=v2;
if (v1<v2) ty=y2;
else sy=y1;
}
for (int y=sy;y<=ty;y++)
{
double t=calc(x0,y);
if (t<R) R=t;
}
return R;
}
int main()
{
while (scanf(“%d”,&n)!=-1 && n!=0)
{
for (int i=0;i<n;i++) scanf(“%d%d”,&x[i],&y[i]);
minx=maxx=x[0];
miny=maxy=y[0];
for (int i=0;i<n;i++)
{
if (x[i]<minx) minx=x[i];
if (x[i]>maxx) maxx=x[i];
if (y[i]<miny) miny=y[i];
if (y[i]>maxy) maxy=y[i];
}
result=1e100;
int sx=minx,tx=maxx;
for (;tx-sx>10;)
{
int x1=sx+(tx-sx)/3;
int x2=tx+(sx-tx)/3;
double v1=calc_byx(x1);
double v2=calc_byx(x2);
if (v1<v2) tx=x2;
else sx=x1;
}
for (int x=sx;x<=tx;x++) calc_byx(x);
printf(“%.6lfn”,result+1e-11);
}
return 0;
}