2011-06-07 17:31:24Morris
d809. 黑暗土地
http://zerojudge.tw/ShowProblem?problemid=d809
內容 ：
黑 暗大陸的野人們突然四散開來，然後一瞬間大家都停了下來，靜止不動。部落首領走了出來，告訴努曼諾爾人這些野人們的座標位置，要求努曼諾爾人選出其中三 個，而選中的那三個野人所圍出來的土地就送給努曼諾爾人。現在，請從首領提供的座標資訊回答：最大的三角形土地面積可以是多少。若三個點的座標為 (a,b), (c,d), (e,f)，則這三個點圍成的三角形面積為：
| 0.5*(ad+cf+be-bc-de-af) |
輸入說明
：
有多組測試資料，以EOF結尾。
輸入的第一行是一個正整數N (3<=N<=200)，表示平面上有多少野人。接下來有N行，每行兩個整數，其中第k行代表第k個野人所在的座標 (Xk,Yk)。
輸出說明
：
輸出可以取得的最大三角形土地面積，請四捨五入到小數點後兩位。
範例輸入 ：
4 0 0 0 1 1 0 1 1 3 1 1 5 3 2 9
範例輸出 ：
0.50 15.00
提示
：
出處
：
(管理：VacationClub)
作法 : 窮舉
O(N^3)
不出知道凸包上的點，去做窮舉，有沒有辦法得到最佳值呢，這樣複雜度又可以大大地下降
不過目前，我的凸包不太行 -ˇ- (應該說，不是正式的凸包寫法，不敢做)
作法 : 窮舉
O(N^3)
不出知道凸包上的點，去做窮舉，有沒有辦法得到最佳值呢，這樣複雜度又可以大大地下降
不過目前，我的凸包不太行 -ˇ- (應該說，不是正式的凸包寫法，不敢做)
/**********************************************************************************/
/* Problem: d809 "黑暗土地" from */
/* Language: C */
/* Result: AC (4ms, 299KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-02 22:34:04 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
struct D{
int x, y;
}s[200];
main() {
int N, a, b, c;
while(scanf("%d", &N) == 1) {
for(a = 0; a < N; a++)
scanf("%d %d", &s[a].x, &s[a].y);
int max = 0, t;
for(a = 0; a < N; a++)
for(b = a+1; b < N; b++)
for(c = b+1; c < N; c++) {
t = abs(s[a].x*s[b].y + s[b].x*s[c].y + s[c].x*s[a].y
-s[a].y*s[b].x - s[b].y*s[c].x - s[c].y*s[a].x
);
if(t > max) max = t;
}
printf("%.2lf\n", max / 2.0);
}
return 0;
}
上一篇：d808. 黑暗部落
下一篇：d810. 大朋友下樓梯