UVA 1331 Minimax Triangulation (dp)

제목: m변형을 주고 m-2개의 삼각형으로 분할하여 가장 큰 삼각형의 면적을 최소화하는 분할 방안에서 이 가장 큰 삼각형의 면적이 얼마나 되는지 구한다.
분석:
본 문제는 삼각형의 분할과 유사하며, dp[i][j]를 점 i에서 j까지 가장 큰 삼각형 면적으로 설정하면 상태 이동 방정식을 얻을 수 있다.

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

상태 이동을 진행하기 전에 이 세 개의 점이 삼각형을 구성할 수 있는지, 즉 이 삼각형에 다른 점이 있는지 판단해야 한다.
세 개의 점을 a, b, c로 설정하고 그 점은 k이다. 만약에 Sabk+Sack+Sbck = Sabc라면 이 점은 이 삼각형 안에 있다는 것을 설명하고 다시 판단할 때 정밀도 오차가 있음을 주의해야 한다.
마지막으로 점차적으로 미루는 방향을 주의해야 한다. i 또는 j가 점차적으로 증가하거나 감소하는 방향에 따라 미루면 안 된다. j-i가 점차적으로 증가하는 순서에 따라 미루어야 한다. 왜냐하면 긴 구간의 결과는 짧은 구간에 의존하기 때문이다.
코드:

#include