結果
問題 | No.2012 Largest Triangle |
ユーザー |
|
提出日時 | 2022-07-15 22:28:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,331 bytes |
コンパイル時間 | 1,598 ms |
コンパイル使用メモリ | 136,412 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-27 21:20:57 |
合計ジャッジ時間 | 9,793 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 40 TLE * 1 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<string> #include<iomanip> #include<numeric> #include<queue> #include<stack> #include<set> #include<map> using namespace std; typedef long long ll; const int mod=1e9+7; int dx[]={1,0,0,-1},dy[]={0,1,-1,0}; //点を表す構造体 struct Point{ int x,y; Point(double x=0,double y=0):x(x),y(y){}; }; //四則演算 Point operator-(Point p1,Point p2){ return Point(p1.x-p2.x,p1.y-p2.y); } //比較演算 bool operator<(Point p1,Point p2){ if(p1.x!=p2.x) return p1.x<p2.x; return p1.y<p2.y; } bool operator>(Point p1,Point p2){ if(p1.y!=p2.y) return p1.y<p2.y; return p1.x<p2.x; } //入出力 istream&operator>>(istream&is,Point&p){ is>>p.x>>p.y; return is; } //ベクトルを表す構造体 typedef Point Vector; //ベクトルのノルム double norm(Vector a){ return (ll)a.x*a.x+(ll)a.y*a.y; } //内積 ll dot(Vector a,Vector b){ return(ll)a.x*b.x+(ll)a.y*b.y; } //外積 ll cross(Vector a,Vector b){ return(ll)a.x*b.y-(ll)a.y*b.x; } //多角形を表すクラス typedef vector<Point>Polygon; //入出力 istream&operator>>(istream&is,Polygon&p){ for(auto&x:p) is>>x; return is; } //CCW constexpr int COUNTER_CLOCKWISE=1; constexpr int CLOCKWISE=-1; constexpr int ONLINE_BACK=2; constexpr int ONLINE_FRONT=-2; constexpr int ON_SEGMENT=0; int ccw(Point p0,Point p1,Point p2){ Vector a=p1-p0,b=p2-p0; if(cross(a,b)>0) return COUNTER_CLOCKWISE; if(cross(a,b)<0) return CLOCKWISE; if(dot(a,b)<0) return ONLINE_BACK; if(norm(a)<norm(b)) return ONLINE_FRONT; return ON_SEGMENT; } //凸包 Polygon andrewScan(Polygon s){ if(s.size()<=1) return s; sort(s.begin(),s.end()); Polygon u,l; u.push_back(s[0]); u.push_back(s[1]); l.push_back(s[s.size()-1]); l.push_back(s[s.size()-2]); for(int i=2;i<s.size();i++){ for(int n=u.size();n>=2&&ccw(u[n-2],u[n-1],s[i])!=CLOCKWISE;n--) u.pop_back(); u.push_back(s[i]); } for(int i=s.size()-3;i>=0;i--){ for(int n=l.size();n>=2&&ccw(l[n-2],l[n-1],s[i])!=CLOCKWISE;n--) l.pop_back(); l.push_back(s[i]); } reverse(l.begin(),l.end()); for(int i=u.size()-2;i>=1;i--) l.push_back(u[i]); return l; } int main(){ int n; cin>>n; Polygon g(n); cin>>g; g=andrewScan(g); ll ans=0; for(auto&x:g) for(auto&y:g) ans=max(ans,cross(x,y)); cout<<ans<<endl; }