CodeChef submission 49716 (C++ 4.0.0-8) plaintext list. Status: AC, problem E3, contest JULY09. By gmark (Mark Greve), 2009-07-06 16:29:11.
// Johnny The Farmer
// Source: CodeChef July 2009 Algorithm Challenge
// CodeChef ID: E3
// Date: 06-07-2009
// Author: Mark Greve
// Keywords: computational geometry, convex hull, maximum area triangle in point set.
// Status: AC
// Difficulty: hard
// Complexity: O(nlogn)
// Comments:
// Damn hard!
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
 
#define REP(i,a,b) for (int i=(a);i<(b);++i) 
bool is0(int x) { return x==0; }
//////////////////////////////////////////////////
struct PT {
	int x,y;
	PT(int a=0, int b=0) : x(a), y(b) {}
	bool operator<(const PT& p) const{return is0(x-p.x)?y<p.y:x<p.x;}
};
 
int side_sign(const PT& p1, const PT& p2, const PT& p3) { // ie. left turn/right turn
	// to which side is p3 of the line p1-> p2. 1 left, 0 on, -1 right.
	int sg = (p1.x-p3.x)*(p2.y-p3.y) - (p1.y-p3.y)*(p2.x-p3.x);
	if (is0(sg)) { return 0; } else { return sg>0 ? 1 : -1; }
}
 
vector<PT> vex(vector<PT> v) { // Don't pass by REFERENCE!
	int n=v.size(), k=0; vector<PT> h(2*n);
	sort(v.begin(), v.end()); // lexicographic sort.
	REP(i,0,n) { // Build lower hull
		while (k>=2 && side_sign(h[k-2],h[k-1],v[i])>=0) --k;
		h[k++] = v[i];
	}
	for (int i=n-2,t=k+1;i>=0;--i) { // Build upper hull
		while (k>=t && side_sign(h[k-2],h[k-1],v[i])>=0) --k;
		h[k++] = v[i];
	} return h.resize(k-1), h;
}
 
int tr(const PT& a, const PT& b) { return (b.x - a.x)*(b.y + a.y); } 
int triarea(const PT& a,const PT& b,const PT& c){return abs(tr(a,b)+tr(b,c)+tr(c,a));}
 
// Returns twice the maximum area of a triangle inscribed in v
// Precondition: v is a convex polygon with |v| >= 3
int maximum_area_triangle(const vector<PT>& v) {
	int n = v.size(), A = 0, B = 1, C = 2, a = 0, b = 1, c = 2;
	do {
		for (;;) {
			while (triarea(v[a],v[b],v[c])<=triarea(v[a],v[b],v[(c+1)%n])) c = (c+1)%n;
			if (triarea(v[a],v[b],v[c])<=triarea(v[a],v[(b+1)%n],v[c])) b = (b+1)%n;
			else break;
		}
		if (triarea(v[a],v[b],v[c])>triarea(v[A],v[B],v[C])) A=a,B=b,C=c;
		a = (a+1)%n;
		if (a==b) b = (b+1)%n;
		if (b==c) c = (c+1)%n;
	} while (a!=0);
	return triarea(v[A], v[B], v[C]);
}
 
int solve() {
	int n;
	scanf("%d", &n);
	vector<PT> v(n);
	for (int i=0;i<n;++i) scanf("%d %d", &v[i].x, &v[i].y);
 
	bool allcoll = 1;
	for (int i=0;i+2<n;++i) {
		if (0!=side_sign(v[i],v[i+1],v[i+2])) {
			allcoll = 0;
			break;
		}
	}
	if (allcoll) return 0;
	
	vector<PT> h = vex(v);
	return maximum_area_triangle(h);
}
 
int main() {
	int NCASES;
	scanf("%d", &NCASES);
	while (NCASES-- > 0) printf("%d\n", solve());
}