如何计算XI Samara区域大学生编程竞赛B题的最小面积？

本文共计742个文字，预计阅读时间需要3分钟。

给定一个严格凸多边形，求由多边形顶点构成的非退化三角形的可能最小面积。输入：第一行包含一个整数n（3 ≤ n ≤ 200000）——多边形的顶点数。

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; }