中南高校2012年8月月赛 Problem D: Di
发布时间： 2012-11-11 10:07:57 作者： rapoo
中南大学2012年8月月赛 Problem D: Distribution 求三角形面积
Problem D: Distribution/*状态压缩记忆化搜索，遍历每个人和某两人组合后与最优子结果的和更新当前状态。 */ #include<stdio.h>#include<string.h>#include<stdlib.h>const int maxn = 22;const int maxd = 1 << 21 | 1;const int inf = 0x3f3f3f3f;typedef struct {int x, y;}Point;Point p[maxn];int dp[maxd];int area[maxn][maxn][maxn];int n;inline int max(int a, int b){return a > b ? a : b;}int CalArea(int i, int j, int k){return abs((p[j].x - p[i].x) * (p[k].y - p[i].y) -(p[k].x - p[i].x) * (p[j].y - p[i].y));}int DPS(int situ){int &ans = dp[situ], i, j, k;if(ans != -1) return ans;if(situ == (1 << n) - 1) return ans = 0;for(i = 0; situ & 1 << i; ++ i);ans = DPS(situ | 1 << i);for(j = i + 1; j < n; ++ j){if(~situ & 1 << j){for(k = j + 1; k < n; ++ k){if(~situ & 1 << k)ans = max(ans, area[i][j][k] + DPS(situ | 1 << i | 1 << j | 1 << k));}}}return ans;}int main(){int i, j, k, S, ans;while(scanf("%d", &n) != EOF){for(i = 0; i < n; ++ i)scanf("%d%d", &p[i].x, &p[i].y);for(i = 0; i < n; ++ i)for(j = i + 1; j < n; ++ j)for(k = j + 1; k < n; ++ k)area[i][j][k] = CalArea(i, j, k);memset(dp, -1, sizeof(int) * (1 << n));printf("%.1f\n", DPS(0) * 0.5);}return 0;}