結果
問題 | No.2331 Maximum Quadrilateral |
ユーザー |
|
提出日時 | 2023-05-09 23:28:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 155 ms / 2,000 ms |
コード長 | 1,286 bytes |
コンパイル時間 | 1,620 ms |
コンパイル使用メモリ | 195,092 KB |
最終ジャッジ日時 | 2025-02-12 21:06:12 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h>using namespace std;// x2int triangle_area(int x1, int y1, int x2, int y2, int x3, int y3){return abs((x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3));}int main(){int n; cin >> n;vector<int> x(n), y(n);for(int i = 0; i < n; i++){cin >> x[i] >> y[i];}int ans = 0;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){int a = (y[j] - y[i]), b = (x[i] - x[j]), c = (y[i] - y[j]) * x[i] + (x[j] - x[i]) * y[i];int mx1 = -1, mx2 = -1;int idx1 = -1, idx2 = -1;for(int k = 0; k < n; k++){if(k == i || k == j) continue;int len = a * x[k] + b * y[k] + c;if(len > 0){if(mx1 < abs(len)){mx1 = abs(len), idx1 = k;}}else{if(mx2 < abs(len)){mx2 = abs(len), idx2 = k;}}}if(mx1 == -1 || mx2 == -1) continue;int res = triangle_area(x[i], y[i], x[j], y[j], x[idx1], y[idx1]) + triangle_area(x[i], y[i], x[j], y[j], x[idx2], y[idx2]);ans = max(ans, res);}}cout << ans << "\n";}