UVa1331 - Minimax Triangulation

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4077

解題策略

dp[i][j]表示字串第i個點到第j個點所形成三角形的最大面積的最小值

i<=k<j，i與j中間至少要有一個點，對每一個k，三角形ijk內不會有多邊形的其他點

dp[i][j]=min(dp[i][j], max(area(i,j,k), dp[i][k], dp[k][j]))

area(i,j,k)為ijk的三角形面積，使用海龍公式

初始化

dp[i][j]為很大的數值