XI Samara Regional Intercollegiate Programming Contest Problem B. Minimal Area 计算几何

You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose
vertices are the vertices of the polygon.
Input
The first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.
Each of the next n lines contains two integers xi and yi (−109 ≤ xi
, yi ≤ 109
) — the coordinates of polygon
vertices.
The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.
Output
It is known that the area of triangle whose vertices are the integer points on the grid is either integer or
half-integer.
Output a single integer — the required area, multiplied by 2.
Examples
standard input standard output
4
0 1
3 0
3 3
-1 3
5
3
0 0
1 0
0 1
1
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
3999999948000000156
Note
It is recommended to make all calculations using integer numbers, because floating point precision most
likely would not be enough.
这次计算几何还挺简单的；
题意：给定一个严格凸多边形，求在凸多边形中找三个点，使得构成的三角形面积最小；
最后输出答案*2；
很明显是相邻的三个点组成的面积最小。。。。。那么只需要绕一圈即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 500005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>



ll quickpow(ll a, ll b) {
    ll ans = 1;
    a = a % mod;
    while (b > 0) {
        if (b % 2)ans = ans * a;
        b = b / 2;
        a = a * a;
    }
    return ans;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

bool prime(int x) {
    if (x == 0 || x == 1)return false;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x%i == 0)return false;
    }
    return true;
}

ll x[maxn], y[maxn];
ll ans = 5e18 + 1;

ll work(ll x1, ll y1, ll x2, ll y2) {
    return abs((ll)x1*y2 - (ll)x2 * y1);
}
int main()
{
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int i, j;
    for (i = 0; i < n; i++)cin >> x[i] >> y[i];
    x[n] = x[0]; x[n + 1] = x[1];
    y[n] = y[0]; y[n + 1] = y[1];
    for (i = 0; i < n; i++) {
        ans = min(ans, work(x[i] - x[i + 1], y[i] - y[i + 1], x[i] - x[i + 2], y[i] - y[i + 2]));

    }
    cout << ans << endl;
}