340B - Maximal Area Quadrilateral - CodeForces Solution

/*
          ,     \    /      ,
         / \    )\__/(     / \
        /   \  (_\  /_)   /   \
   ____/_____\__\@  @/___/_____\____
  |             |\../|              |
  |              \VV/               |
  |        ------hoi-------         |
  |_________________________________|
   |    /\ /      \\       \ /\    |
   |  /   V        ))       V   \  |
   |/     `       //        '     \|
   `              V                '
*/

#include <bits/stdc++.h>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define ld long double
#define f first
#define s second
#define mp make_pair
#define Speedforce boost();

using namespace std;

void boost(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const int N = 1e6 + 123;
const ll MOD = 1e9 + 7;

ll bin_pow(ll base, ll k, ll mod = MOD){
    ll ans = 1;
    while(k){
        if(k % 2){
            ans *= base;
            ans %= mod;
        }
        base *= base;
        base %= mod;
        k/=2;
    }
    return ans % mod;
}

ld len(pair <ld, ld> x, pair <ld, ld> y){
    return (x.f - y.f) * (x.f - y.f) + (x.s - y.s) * (x.s - y.s);
}

void solve(){
    int n;
    cin >> n;
    pair <ld, ld> a[n + 5];
    for(int i = 1;i <= n;i ++){
        cin >> a[i].f >> a[i].s;
    }
    long double ans = 0;
    for(int i = 1;i <= n;i ++){
        int y = i;
        //cout << i << endl;
        for(int j = 1;j <= n;j ++){
            if(len(a[i], a[y]) < len(a[i], a[j])){
                y = j;
            }
        }
        for(int j = 1;j <= n;j ++){
            if(j == i || j == y){
                continue;
            }
            for(int k = 1;k <= n;k ++){
                if(k == i || k == j || k == y){
                    continue;
                }
                //cout << i << " " << j << " " << y << " " << k << endl;
                //cout << abs((a[i].f-a[j].s) * (a[i].f + a[j].s) + (a[j].f - a[y].f) * (a[j].s + a[y].s) + (a[y].f - a[k].f) * (a[y].s + a[k].s) + (a[k].f - a[i].f) * (a[k].s + a[i].s))/2 << endl;
                ans = max(ans, (a[i].f * a[j].s - a[i].s * a[j].f + a[j].f * a[y].s - a[j].s * a[y].f + a[y].f * a[k].s - a[y].s * a[k].f + a[k].f * a[i].s - a[k].s * a[i].f)/2);
            }
        }
    }
    cout << fixed << setprecision(6) << ans;
}

int main() {
    srand(time(0));
    Speedforce
    int t = 1;
    //cin >> t;
    while(t--){
        //cout << "A" << endl;
        solve();
    }
}