NKPOLY - Chia đa giác
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static long[] x, y;
static long[][] F;
static long S(int i,int j,int k) {
return Math.abs((x[i]-x[j])*(y[i]+y[j])+(x[j]-x[k])*(y[j]+y[k])+(x[k]-x[i])*(y[k]+y[i]));
}
static long tinh(int i,int j) {
if(i+1>=j) return 0;
if(F[i][j]!=-1) return F[i][j];
int t = i+1;
long res = 1000000000000000L;
for(;t<j;++t) {
res = Math.min( res, Math.max(tinh(i,t), Math.max( tinh(t,j), S(i,j,t)) ));
}
return F[i][j] = res;
}
public static void main(String[] args) throws Exception {
BufferedReader kb = new BufferedReader( new InputStreamReader(System.in));
int n = Integer.parseInt(kb.readLine());
StringTokenizer st;
x = new long[n];
y = new long[n];
for(int i=0;i<n;++i) {
st = new StringTokenizer(kb.readLine());
x[i] = Long.parseLong(st.nextToken());
y[i] = Long.parseLong(st.nextToken());
}
long max = 0;
for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) for(int k=j+1;k<n;++k) max = Math.max( max, S(i,j,k));
System.out.printf("%.1f\n", max/2.0);
F = new long[n][n];
for(long[] aa : F) Arrays.fill( aa, -1);
long res2 = tinh(0,n-1);
System.out.printf("%.1f\n", res2/2.0);
}
}