結果

問題 No.2331 Maximum Quadrilateral
ユーザー KKT89KKT89
提出日時 2023-05-28 14:58:23
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,907 bytes
コンパイル時間 4,056 ms
コンパイル使用メモリ 222,716 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-27 03:48:41
合計ジャッジ時間 4,270 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

const double eps=1e-10;

struct point{
    ll x,y;
    point() {}
    point(ll x,ll y): x(x), y(y) {}
    point& operator-=(const point &p){
        x -= p.x; y -= p.y;
        return *this;
    }
    point& operator+=(const point &p){
        x += p.x; y += p.y;
        return *this;
    }
    point& operator*=(double d){
        x *= d; y *= d;
        return *this;
    }
    point& operator/=(double d){
        x /= d; y /= d;
        return *this;
    }
    const point operator+ (const point& p) const;
    const point operator- (const point& p) const;
    const point operator* (double d) const;
    const point operator/ (double d) const;
};
const point point::operator+ (const point& p) const{
    point res(*this); return res += p;
}
const point point::operator- (const point& p) const{
    point res(*this); return res -= p;
}
const point point::operator* (double d) const{
    point res(*this); return res *= d;
}
const point point::operator/ (double d) const{
    point res(*this); return res /= d;
}

struct line{
    point A,B;
    line() {}
    line(point A, point B): A(A), B(B) {}
};
// A+B
point sum(point A,point B){
    A.x+=B.x; A.y+=B.y; return A;
}
// A-B
point sub(point A,point B){
    A.x-=B.x; A.y-=B.y; return A;
}
// A to B
point vec(line L){
    return (L.B - L.A);
}

ll dot(point a,point b){
    return a.x*b.x+a.y*b.y;
}

ll cross(point a,point b){
    return a.x*b.y-a.y*b.x;
}

int ccw(point a,point b,point c){
    b={b.x-a.x,b.y-a.y};
    c={c.x-a.x,c.y-a.y};
    if(cross(b,c)>eps)return 1; // a,b,c反時計回り
    if(cross(b,c)<-eps)return -1; // a,b,c時計周り
    if(dot(b,c)<-eps)return 2; // c,a,b 一直線
    if((b.x*b.x+b.y*b.y)<(c.x*c.x+c.y*c.y))return -2; // a,b,c 一直線
    return 0; // a,c,b 一直線
}

// 凸包
// AOJ 2827
vector<point> convex_hull(vector<point> ps){
    int n = ps.size();
    int k = 0; // 凸包の頂点数
    sort(ps.begin(), ps.end(), [&](auto p, auto q){
        if(p.x < q.x - eps) return true;
        if(p.x > q.x + eps) return false;
        return p.y < q.y;
    });
    vector<point> qs(2*n); // 構築中の凸包
    for(int i=0;i<n;qs[k++]=ps[i++]){
        while(k>=2&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k;
    }
    for(int i=n-2,t=k+1;i>=0;qs[k++]=ps[i--]){
        while(k>=t&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k;
    }
    qs.resize(k-1);
    return qs;
}

// AOJ-2160
// 多角形の符号付き面積(反時計回りが正)
ll area(vector<point> g){
    ll res=0.0;
    for(int i=0;i+1<g.size();i++){
        res+=cross(g[i],g[(i+1)]);
    }
    // ここは未verify
    if(res < eps){
        res = -res;
    }
    return res;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<point> p(n);
    for (int i = 0; i < n; ++i) {
        int x,y; cin >> x >> y;
        p[i] = point(x,y);
    }
    auto ps = convex_hull(p);
    if (ps.size() >= 4) {
        p = ps;
    }
//    p = convex_hull(p);
    ll res = 0;
    n = p.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            for (int k = j+1; k < n; ++k) {
                for (int l = k+1; l < n; ++l) {
                    res = max(res, area(vector<point>{p[i],p[j],p[k],p[l],p[i]}));
                    res = max(res, area(vector<point>{p[i],p[k],p[j],p[l],p[i]}));
                    res = max(res, area(vector<point>{p[i],p[j],p[l],p[k],p[i]}));
                }
            }
        }
    }
    cout << res << endl;
}
0