#4719. 내부 볼륨

코드

#include 
using namespace std;
int T,n,m,s,f[55][55],c[55];
struct O{int x,y;}b[55],a[55];
O operator -(O A,O B){
	return (O){A.x-B.x,A.y-B.y};
}
int operator *(O A,O B){
	return A.x*B.y-A.y*B.x;
}
int S(O A){
	return A.x*A.x+A.y*A.y;
}
bool cmp(O A,O B){
	return A*B<0 || (A*B==0 && S(A)<S(B));
}
void W(){
	memset(f,0,sizeof f);
	sort(a+1,a+m+1,cmp);
	for (int j,k,t,v,i=2;i<=m;i++){
		j=i-1;t=0;
		while(j && a[j]*a[i]==0) j--;
		while(j){
			c[++t]=j;k=j-1;v=a[i]*a[j];
			while(k && (a[k]-a[j])*(a[i]-a[j])<0) k--;
			if (k) v+=f[j][k];
			f[i][j]=v;s=max(v,s);j=k;
		}
		for (int u=t-1;u>0;u--)
			f[i][c[u]]=max(f[i][c[u]],f[i][c[u+1]]);
	}
}
void work(){
	scanf("%d",&n);s=0;
	for (int i=1;i<=n;i++)
		scanf("%d%d",&b[i].x,&b[i].y);
	for (int i=1;i<=n;i++){
		m=0;
		for (int j=1;j<=n;j++){
			if (b[j].y>b[i].y || (b[j].y==b[i].y && b[j].x>b[i].x))
				a[++m]=b[j]-b[i];
		}
		W();
	}
	printf("%.1lf
",1.*s/2);
}
int main(){for (cin>>T;T--;work());return 0;}