d809 - 黑暗土地
題目描述
題目要求從給定的 N 個點中選出三個點，使得這三個點構成的三角形面積最大。輸入包含 N (3 <= N <= 200) 個點的座標，輸出最大三角形面積，精確到小數點後兩位。
解題思路
由於點的數量較少 (N <= 200)，可以使用暴力解法。枚舉所有可能的三個點的組合，計算每個組合所構成的三角形面積，並記錄最大面積。三角形面積的計算公式已在題目中給出。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是點的數量。因為需要枚舉所有可能的三個點的組合，即 C(n, 3) = n * (n-1) * (n-2) / 6，這是一個關於 n 的三次多項式。
- 空間複雜度: O(n)，用於儲存點的座標。
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
double b[201][2];
int main(){
int a;
while(cin >> a){
for(int i=0;i<a;++i)
cin >> b[i][0] >> b[i][1];
double max=0;
for(int i=0;i<a;++i){
for(int j=i+1;j<a;++j){
for(int k=j+1;k<a;++k){
double t=0.5*(b[i][0]*b[j][1]+b[j][0]*b[k][1]+b[i][1]*b[k][0]-b[i][1]*b[j][0]-b[j][1]*b[k][0]-b[i][0]*b[k][1]);
if(t<0)t*=-1;
if(t>max)max=t;
}
}
}
cout << fixed << setprecision(2) << max << "\n";
}
}