結果
問題 | No.2331 Maximum Quadrilateral |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:54:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 500 ms / 2,000 ms |
コード長 | 1,370 bytes |
コンパイル時間 | 2,107 ms |
コンパイル使用メモリ | 198,968 KB |
最終ジャッジ日時 | 2025-02-13 12:13:37 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define double long doubleint f(int x1, int y1, int x2, int y2, int x3, int y3) {int area = abs((x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)));return area;}bool ff(int x1, int y1, int x2, int y2, int x3, int y3) {double epsilon = 1e-9; // 許容誤差// 直線ABの傾きを計算double slopeAB = 1.0*(y2 - y1) / (x2 - x1);// 直線ABの方程式を用いて、点Cのy座標を予測double predictedY = y1 + 1.0 * slopeAB * (x3 - x1);// 点Cのy座標と実際のy座標の差を比較して判定if (predictedY > y3) {return true; // Cは直線AB上にある} else {return false; // Cは直線AB上にない}}signed 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++){vector<int> A = {}, B = {};for(int k=0;k<N;k++){if(i == k || j == k) continue;if(ff(X[i],Y[i],X[j],Y[j],X[k],Y[k])) A.push_back(f(X[i],Y[i],X[j],Y[j],X[k],Y[k]));else B.push_back(f(X[i],Y[i],X[j],Y[j],X[k],Y[k]));}int a = 0;for(int x:A) a = max(a,x);int b = 0;for(int y:B) b = max(b,y);//cout<<i<<' '<<j<<' '<<a<<' '<<b<<endl;if(a == 0 || b == 0) continue;ans = max(ans,a+b);}cout<<ans<<endl;}