vva 1543 - Telescope(dp+ 형상)

제목 링크: uva 1543 - Telescope
제목의 대의: 시계 반대 순서에 따라 단위 원의 점(백분율)을 제시한 다음에 k를 주고 k개의 점으로 구성된 다각형의 면적이 가장 크고 출력이 가장 큰 값을 선택하도록 요구한다.
문제풀이 사고방식: 처음에 방향을 잘못 생각하고 컨디션을 다 생각해 봤는데 면적을 어떻게 구해야 할지 모르겠어요. 원심과 원상 두 가지를 말해서 면적을 구하려고 했지만 이렇게 하면 원형이 다각형 외부에 있을 가능성이 있어요.나중에 헬렌 공식을 생각해 보니 세 변의 길이에 따라 면적을 구하고 그 다음에 원은 고리 모양이었다.그래서 dp수조를 배로 확대합니다.dp[i][j][k]는 i점부터 j점까지 k점의 최대 면적을 선택한다(i, j는 반드시 선택해야 한다)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 50;
const double pi = atan(1.0) * 4;

int n, k;
double dp[N][N][N];
double p[N], d[N][N], area[N][N][N];

inline double dis(int x, int y) {
	double a = p[y] - p[x];

	if (a > 0.5)
		a = 1 - a;
	return 2 * sin(a*pi);
}

inline double getArea(double x, double y, double z) {
	double tmp = (x + y + z)/2;
	return sqrt(tmp * (tmp - x) * (tmp - y) * (tmp - z));
}

void init () {
	for (int i = 0; i < n; i++)
		scanf("%lf", &p[i]);

	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			d[i][j] = d[j][i] = dis(i, j);

	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			for (int t = j+1; t < n; t++) {
				double tmp = getArea(d[i][j], d[j][t], d[t][i]);
				area[i][j][t] = area[i][t][j] = tmp;
				area[j][i][t] = area[j][t][i] = tmp;
				area[t][i][j] = area[t][j][i] = tmp;
			}
		}
	}
}

double solve () {
	memset(dp, 0, sizeof(dp));

	for (int i = 3; i <= k; i++) {
		for (int x = 0; x < n; x++) {
			for (int y = x+1; y < n; y++) {

				for (int z = y+1; z < n; z++)
					dp[x][z][i] = max(dp[x][z][i], dp[x][y][i-1] + area[x][y][z]);
			}
		}
	}

	double ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			ans = max(ans, dp[i][j][k]);
		}
	}
	return ans;
}

int main () {
	while (scanf("%d%d", &n, &k) == 2 && n + k) {
		init ();
		printf("%.6lf
", solve());
	}
	return 0;
}