SRM 704 Div1 easy : TreeDistanceConstruction

問題概要：
次の制約を満たすような木は存在するか？

1. 木の頂点iのeccentricityがちょうどd[i]である.

ここで、頂点iのeccentricityとは、頂点iから最も遠い頂点との距離のことである.
存在するのであればその木の辺集合を配列にして返すこと.
存在しないのであれば空の配列を返すこと.

制約：
頂点数は高々50

解法：
答えとなる木の中で、最も離れている頂点対(i,j)について考える.
この２点をつなぐ長さd[i]のパスが存在するはずなので、そのパスを用意する.
そのパス上の最も離れた頂点対以外の頂点になりうる入力中の頂点が存在するはずなので、
それらを見つけてパスの頂点と対応付ける.
あとは入力中のまだどこにも対応付けられていない頂点を、そのパス上の適切な頂点に繋げればよい.
適切な頂点というのは、頂点iのeccentricityがd[i]であるときeccentricityがd[i]-1であるような頂点のことである.
マイナス1してあるのは、その頂点に辺を張ることでeccentricityが1増えるため.
残った頂点のeccentricityは最もd[i]以下かつ(パスの長さ)/2より大きいはずである.

例えば、Examplesの0)について考えてみる.
Examples 0) の入力は {3,2,2,3}なので、最も離れている頂点対は(0,3)である(0-indexed).
それでは、まず最初にこの２点をつなぐパスを作る.
このパスは以下の図のようになる.

最も離れている頂点対以外のパス上の頂点のeccentricityは？となっているが、
これらのeccentricityは明らかに2である.

この例だとこれで条件を満たす木ができたので終わり.

Examples 1)についても考えて見る.
入力は {1,2,2,2}である.
まず最初に最も離れている頂点対からパスを作る.

次にパスの中のでまだ入力中の頂点と対応付けられていない頂点に対して入力中の頂点を対応付ける.

あとは、残った入力中の頂点1をパス上の適切な頂点に繋げればよい.
頂点1のeccentricityは2なので、パス上のeccentricityが1の頂点に繋げばよい.

最後に、Examplesにはないが少し大きめの例について考えて見る.
入力は{4,4,3,2,3,4,4,3}とする.
まず最初に最も離れている頂点対からパスを作る.

次に、パス上の頂点と入力上の頂点を対応付ける

最後に、入力中の残った頂点をパス上の適切な頂点に繋げる.
まず、頂点5はeccentricityが4であるため、eccentricityが3であるような頂点に繋げば良い.

頂点6もeccentricityが4であるため、eccentricityが3であるような頂点に繋げば良い.

最後に、頂点7のeccentricityは3なので、eccentricityが2であるような頂点に繋ぐ.

完成である.

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

struct Data {
  int index;
  int eccentricity;
  bool operator < ( const Data &data ) const {
    return eccentricity > data.eccentricity;
  }
};

class TreeDistanceConstruction {
public:
  vector <int> construct(vector <int> d) {
    deque<Data> deq;
    int n = d.size();
    rep(i,n) deq.push_back((Data){i,d[i]});
    d.clear();
    sort(deq.begin(),deq.end());
    int maxi = deq[0].eccentricity;

    if( maxi != deq[1].eccentricity ) return vector<int>();
    vector<vector<int>> G;
    int root = (maxi+1) / 2;
    rep(i,(maxi+1)) {

      G.push_back(vector<int>());

      G[i].push_back(-1); // G[i][0], index

      if( (maxi+1) & 1 ) { // G[i][1], eccentricity
	if( i <= root ) G[i].push_back(maxi-i);
	else            G[i].push_back(i);
      } else {
	if( i < root ) G[i].push_back(maxi-i);
	else            G[i].push_back(i);
      }
      
      if( i + 1 < (maxi+1) ) G[i].push_back(i+1);
      if( i - 1 >= 0 ) G[i].push_back(i-1);

    }
    
    G[0][0] = deq.front().index; deq.pop_front();
    G[(int)G.size()-1][0] = deq.front().index; deq.pop_front();

    REP(i,1,(int)G.size()-1) {
      int pos = -1;
      rep(j,(int)deq.size()) {
	if( deq[j].eccentricity == G[i][1] ) {
	  pos = j;
	  break;
	}
      }
      if( pos == -1 ) return vector<int>();
      G[i][0] = deq[pos].index;
      deq.erase(deq.begin()+pos);
    }
    
    rep(i,(int)deq.size()) {
      if( deq[i].eccentricity <= root ) return vector<int>();
      G.push_back(vector<int>());
      G[(int)G.size()-1].push_back(deq[i].index);
      G[(int)G.size()-1].push_back(deq[i].eccentricity);
      G[(int)G.size()-1].push_back(deq[i].eccentricity-1);
      G[deq[i].eccentricity-1].push_back((int)G.size()-1);
    }

    vector<int> answer;
    rep(i,(int)G.size()) {
      REP(j,2,(int)G[i].size()) {
	int s = G[i][0];
	int t = G[G[i][j]][0];
	if( s < t ) {
	  answer.push_back(s);
	  answer.push_back(t);
	}
      }
    }
    return answer;
  }
};

LiveArchive 5873 : Tree Inspections

問題リンク : https://icpcarchive.ecs.baylor.edu/external/58/5873.pdf

問題概要 :
２次元平面上にT本の木とH本の道が存在する.
T本の木のうち60%以上を道の上から見ることはできるだろうか？
木は以下の条件を満たすとき、道から見ることができる :
道から垂直に木まで線を引いた際に、その間に他の木が立っていない.

例えば、Sample Input は次のようになる.
黒い点が木を、赤い線が道を表す.

制約 :
1 <= T,P <= 10^5

解法 :
各木について、その木が道から見ることができるかどうかを確かめる
ただし愚直に実装すると T * P ( = 10^10 ) となり間に合わない
そこで、ある木が見えるかどうかを判定する際には、その木に最も近い上下左右の木のみを用いる

つまり、その木に最も近い上下左右の木を求め、その木と最も近い上下左右の木のいずれかとの間に道が存在するかどうかを判定する
これなら全体でもT * 4 * logPとなり間に合う

例えば、以下のようなケースについて考える

赤い点が今見えるかどうかを判定したい木とする
このとき、この木が見えるかどうかの判定に必要な木は青い点として表されている以下の３本である

これらの青い点はlower_boundで求めることができる


あとはその木とlower_boundで求めた木の間に道があるかどうかをlower_boundで求める

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LTE(double a,double b) { return equals(a,b) || a < b; }

const int IINF = INT_MAX;

struct Data {
  int x,y;
};

int dx[] = {0,1,0,-1}; // ↓→↑←
int dy[] = {1,0,-1,0};

int T, P;

bool cmp_x(const Data &v1, const Data &v2) {
  if( v1.x != v2.x ) return v1.x < v2.x;
  return v1.y < v2.y;
}

bool cmp_y(const Data &v1, const Data &v2) {
  if( v1.y != v2.y ) return v1.y < v2.y;
  return v1.x < v2.x;
}

#define ALL(x) x.begin(),x.end()

void compute(vector<Data> &vec, vector<int> &hs, vector<int> &vs) {
  vector<Data> adj[4];
  vector<Data> xs,ys;
  rep(i,T) xs.push_back(vec[i]), ys.push_back(vec[i]);
  sort(ALL(xs),cmp_x);
  sort(ALL(ys),cmp_y);
  sort(ALL(hs));
  sort(ALL(vs));

  rep(i,T) {
    // ↓ xは同じ y+
    int ptr = lower_bound(ALL(xs),vec[i],cmp_x) - xs.begin();
    ++ptr;
    if( ptr < T && xs[ptr-1].x == xs[ptr].x ) {
      adj[0].push_back(xs[ptr]);
    } else {
      adj[0].push_back((Data){vec[i].x,IINF});
    }
    
    // → yは同じ x+
    ptr = lower_bound(ALL(ys),vec[i],cmp_y) - ys.begin();
    ++ptr;
    if( ptr < T && ys[ptr-1].y == ys[ptr].y ) {
      adj[1].push_back(ys[ptr]);
    } else {
      adj[1].push_back((Data){IINF,vec[i].y});
    }


    // ↑ xは同じ y-
    ptr = lower_bound(ALL(xs),vec[i],cmp_x) - xs.begin();
    --ptr;
    if( ptr >= 0 && xs[ptr+1].x == xs[ptr].x ) {
      adj[2].push_back(xs[ptr]);
    } else {
      adj[2].push_back((Data){vec[i].x,-IINF});
    }

    // ← yは同じ x-
    ptr = lower_bound(ALL(ys),vec[i],cmp_y) - ys.begin();
    --ptr;
    if( ptr >= 0 && ys[ptr+1].y == ys[ptr].y ) {
      adj[3].push_back(ys[ptr]);
    } else {
      adj[3].push_back((Data){-IINF,vec[i].y});
    }
  }

  vector<bool> ok(T,false);
  rep(i,T) {
    bool see = false;
    rep(j,4) {
      Data point = adj[j][i];
      if( point.x == vec[i].x ) {
	int pos = lower_bound(ALL(hs),min(vec[i].y,point.y)) - hs.begin();

	if( pos >= (int)hs.size() ) continue;
	if( min(point.y,vec[i].y) <= hs[pos] && hs[pos] <= max(point.y,vec[i].y) ) {
	  see = true;
	  break;
	}
      } else {
      	int pos = lower_bound(ALL(vs),min(vec[i].x,point.x)) - vs.begin();
	if( pos >= (int)vs.size() ) continue;
	if( min(point.x,vec[i].x) <= vs[pos] && vs[pos] <= max(point.x,vec[i].x) ) {
	  see = true;
	  break;
	}
      }
    }
    if( see ) ok[i] = true;
  }
  double cnt = 0;
  rep(i,T) cnt += ok[i];
  if( LTE(0.6,cnt/(double)T) ) {
    puts("PASSED");
  } else {
    puts("FAILED");
  }
}

int main() {
  int F;
  while( cin >> F ) {
    rep(_,F) {
      cin >> T >> P;
      vector<Data> vec(T);
      vector<int> hs,vs;
      rep(i,T) cin >> vec[i].x >> vec[i].y;
      rep(i,P) {
	char c;
	int v;
	cin >> c >> v;
	if( c == 'H' ) hs.push_back(v);
	else           vs.push_back(v);
      }
      compute(vec,hs,vs);
    }
  }
  return 0;
}

CODE FESTIVAL 2016 予選B : D - Greedy customers

問題リンク :
D: Greedy customers - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 日本語なので略

解法 :
(備忘録）
貪欲法。

１ずつ引いていけば良い？1を引けなくなったら2を、それもダメなら3を、...という流れで、
=> Sample Input 2 の答えが13になる
これでダメなケースとは？
...
Sample Input X

4
1
2
6
10

Sample Output X

4

Why?

1 2 6 10  P
1 2 3 10 (3)
1 2 3 6  (4)
1 2 3 2  (4)
Ans : 3.

1 2 6 10  P
1 2 1 10 (5)
1 2 1 7  (3)
1 2 1 4  (3)
1 2 1 1  (3)
Ans : 4.

引ける最小の値が大きくなってしまうような場合は一気に1まで値を引いてしまえばよいネ

コード :

#include<bits/stdc++.h>
 
using namespace std;

#define MAX 100010

int N;
long long A[MAX];
 
int main(){
  long long answer = 0, lower = 1LL;
  cin >> N;
  for(int i=0;i<N;++i) cin >> A[i];

  for(int i=0;i<N;++i) {
    if( lower == 1LL ) {
      answer += (A[i]-1LL);
      lower = 2LL;
      continue;
    }
    
    if( lower == A[i] ) {
      ++lower;
      continue;
    }
 
    if( lower > A[i] ) continue;    
 
    long long coef = A[i] / lower;
    if( ( A[i] - coef * lower ) == 0LL ) {
      --coef;
    }
    answer += coef;
  }
  cout << answer << endl; 
  return 0;
}

CODE FESTIVAL 2016 予選B : C - Gr-idian MST

問題リンク :
C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 :
日本語なので略

解法 :
(ほぼ備忘録)
クラスカル法。
ただし、辺が多すぎて愚直に列挙することはできない。
そこで、この問題では行または列ごとに辺の重みが決まっていることを利用する。

最小の行または列を見つけて、それらを舗装してしまう。
ただし、既に連結であるようなものは舗装しない(舗装した行の数と列の数を別々に覚えておいてそれを引けば良い、詳しくは下の例で)。
Sample Input2の実行例を以下に示す。
赤線が舗装した道を表す。

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

#define DIR_W false
#define DIR_H true

struct Data {
  ll v;
  bool dir;
  bool operator < (const Data &data) const {
    if( v != data.v ) return v < data.v;
    return dir < data.dir;
  }
};

#define MAX 100010

int W,H;
ll p[MAX], q[MAX];

void compute() {
  vector<Data> vec;
  rep(i,W) vec.push_back((Data){p[i],DIR_W});
  rep(i,H) vec.push_back((Data){q[i],DIR_H});
  sort(vec.begin(),vec.end());
  int used_H = 0, used_W = 0;
  ll mini = 0;
  rep(i,(W+H)) {
    if( vec[i].dir == DIR_W ) {
      mini += ( (H+1) - used_H ) * vec[i].v;
      ++used_W;
    } else {
      mini += ( (W+1) - used_W ) * vec[i].v;
      ++used_H;
    }
  }
  cout << mini << endl;
}

int main() {
  cin >> W >> H;
  rep(i,W) cin >> p[i];
  rep(i,H) cin >> q[i];
  compute();
  return 0;
}

CODE FESTIVAL 2016 予選B : B - Qualification simulator

問題リンク :
B: Qualification simulator - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 略

解法 :
既に通過した国内の学生と海外の学生の数を変数に保持しながらループを回します。

コード :

#include<iostream>

using namespace std;

const string YES = "Yes";
const string NO  = "No";

int main() {
  int N,A,B;
  string S;
  cin >> N >> A >> B >> S;
  int a = 0,b = 0;
  for(int i=0;i<N;++i) {
    if( S[i] == 'a' ) {
      if( a+b < A+B ) cout << YES << endl,++a;
      else            cout << NO << endl;
    } else if( S[i] == 'b' ) {
      if( a+b < A+B && b < B ) cout << YES << endl, ++b;
      else                     cout << NO << endl;
    } else {
      cout << NO << endl;
    }
  }
  return 0;
}

CODE FESTIVAL 2016 予選B : A - Signboard

問題リンク :
A: Signboard - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 略

解法 :
ループを回します。

コード :

#include<iostream>

using namespace std;

int main() {
  string s = "CODEFESTIVAL2016",t;
  getline(cin,t);
  int mini = 0;
  for(int i=0;i<(int)s.size();++i) if( s[i] != t[i] ) ++mini;
  cout << mini << endl;
  return 0;
}

LiveArchive 6503 : Golf Field

問題文 : https://icpcarchive.ecs.baylor.edu/external/65/6503.pdf

問題概要 :
２次元平面上にn個の点がある. ( 4 <= n <= 30,000 )
この中から異なる４点を選び凸包を作る.
得られる凸包の面積の最大値を求めよ.

解法 :
凸包 + キャリパー法 + 三分探索

以下の問題の完全上位互換
ncastar.hatenablog.com

解法は基本的に同じだが、
上記の問題よりも頂点数が多くなっているため愚直に２重ループを回せない
そのため２重ループの代わりにキャリパー法を使う

コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
 
using namespace std;
 
// Geo --->
 
class Point{
public:
  double x,y;
 
  Point(double x = 0,double y = 0): x(x),y(y){}
 
  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }
 
  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }
 
  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }
 
};
 
struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator <  (const Segment& s) const { return ( p2 == s.p2 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ) || ( s.p1 == p2 && s.p2 == p1 ); }
 
};
 
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
 
ostream& operator << (ostream& os,const Point& a){ return os << "(" << a.x << "," << a.y << ")"; }
 
ostream& operator << (ostream& os,const Segment& a){ return os << "( " << a.p1 << " , " << a.p2 << " )"; }
 
double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
 
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
 
double norm(Point a){ return a.x*a.x+a.y*a.y; }
 
double abs(Point a){ return sqrt(norm(a)); }
 
//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }
 
// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }
 
// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}
 
int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}
 
bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}
 
Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}
 
double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}
 
double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}
 
Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]); //同じセグメントかもよ
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}
 
Polygon andrewScan(Polygon s)
{
  Polygon u,l;
  if(s.size() < 3)return s;
 
  sort(s.begin(),s.end());
 
  u.push_back(s[0]);
  u.push_back(s[1]);
  l.push_back(s[s.size()-1]);
  l.push_back(s[s.size()-2]);
 
  for(int i=2;i<s.size();i++)
    {
      for(int n=u.size();n >= 2 && ccw(u[n-2],u[n-1],s[i]) != CLOCKWISE; n--)
    u.pop_back();
      u.push_back(s[i]);
    }
 
  for(int i=s.size()-3; i>=0 ; i--)
    {
      for(int n=l.size(); n >= 2 && ccw(l[n-2],l[n-1],s[i]) != CLOCKWISE; n--)
    l.pop_back();
      l.push_back(s[i]);
    }
 
  reverse(l.begin(),l.end());
 
  for(int i = u.size()-2; i >= 1; i--) l.push_back(u[i]);
 
  return l;
}
 
double heron(Point pa,Point pb,Point pc) {
  double a = abs(pa-pb);
  double b = abs(pb-pc);
  double c = abs(pc-pa);
  double s = ( a + b + c ) / 2.0;
  return sqrt( s * ( s - a ) * ( s - b ) * ( s - c ) );
}
 
double LT(double a,double b) { return !equals(a,b) && a < b; }
double LTE(double a,double b) { return equals(a,b) || a < b; }
// Geo <---
 
int n;
 
 
double ternarySearch(int a,int b,vector<Point> &ps){
  int nV = (int)ps.size();
  int L = 1, R = ( a > b ) ? ( ( a - b - 1 + nV ) % nV ) : ( ( ( a + nV ) - b - 1  ) % nV );
  int sp = b;
  int pL = L, pR = R;
 
  rep(_,120){
    if( LT(heron(ps[((L+R*2)/3+sp)%nV],ps[a],ps[b]),heron(ps[((L*2+R)/3+sp)%nV],ps[a],ps[b])) ) {
      R = ( L + R * 2 ) / 3;
    } else {
      L = ( L * 2 + R ) / 3;
    }
    if( R == pR && L == pL ) break;
    pR = R, pL = L;
  }
  return heron(ps[(int)(((L+R)*0.5)+sp)%nV],ps[a],ps[b]);
}
 
bool cmp_x(const Point &p,const Point &q) {
  if( p.x != q.x ) return p.x < q.x;
  return p.y < q.y;
}
 
void compute(vector<Point> &ps) {
  ps = andrewScan(ps);
  double maxi = 0.0;
  n = ps.size();
  if( n == 2 ) assert(false);
  int i = 0, j = 0;
  rep(k,n) {
    if( !cmp_x(ps[i],ps[k]) ) i = k;
    if(  cmp_x(ps[j],ps[k]) ) j = k;
  }
 
  int si = i, sj = j;
  while( i != sj || j != si ) {
    maxi = max(maxi,ternarySearch(i,j,ps)+ternarySearch(j,i,ps));
    if( cross(( ps[(i+1)%n] - ps[i] ),( ps[(j+1)%n]-ps[j])) < 0 ) {
      i = ( i + 1 ) % n;
    } else {
      j = ( j + 1 ) % n;
    }
  }
  printf("%.1f\n",maxi);
}
 
int main() {
  int T;
  while( cin >> T ) {
    while( T-- ) {
      cin >> n;
      vector<Point> ps(n);
      rep(i,n) cin >> ps[i].x >> ps[i].y;
      compute(ps);
    }
  }
  return 0;
}