b288 - 夏季大三角
題目描述
題目給定 N 個點的座標，要求找出其中三個點所構成的最大三角形面積。
解題思路
此題採用暴力解法。由於點的數量不多 (N <= 1000)，我們可以枚舉所有可能的三個點的組合，計算每個組合所形成的三角形面積，並記錄下最大面積。三角形面積的計算使用行列式公式。
複雜度分析
- 時間複雜度: O(n^3) (需要遍歷所有 n*(n-1)*(n-2)/6 種組合)
- 空間複雜度: O(n) (儲存座標點的陣列)
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
double b[1001][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(6) << max << "\n";
}
}