結果
問題 | 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; // x2 int 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"; }