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
Sample 1
Inputcopy
4
0 1
3 0
3 3
-1 3
Outputcopy
5
Sample 2
Inputcopy
3
0 0
1 0
0 1
Outputcopy
1
Sample 3
Inputcopy
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
Outputcopy
3999999948000000156
生词积累:
convex
凸面的 凸多边形的 凸出的 polygon
多边形物体 多角形物体 non-degenerate triangle
简单三角形 vetices
顶点
coordinates
坐标 counterclockwise
顺时针 grid
布局
题意
有一个由n个点组成的多边形,给出这n个点坐标,求由这n个点其中的三个点为顶点的三角形最小面积。
思路
相邻的三个点组成一个三角形,把每个点为始点,与其后两个点组成的三角形面积求出来,取最小值。(到第n个点时,不要忘记它与第一个点和第二个点组成的三角形)
这个算法的时间复杂度不是很高,基本上是O(n)的,所以完全能够满足时间复杂度方面的要求重点就是这个由三个点坐标求三角形面积的方法一定要熟练掌握:
三角形的面积=abs( (x2-x1)(y3-y1)-(y2-y1)(x3-x1))
其中三角形的三个顶点分别为(x1,y1)(x2,y2)(x3,y3)
code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll mianji(ll x1,ll y1,ll x2,ll y2)
{
ll ans=abs(x1*y2-y1*x2);
return ans;
}
struct no
{
ll x,y;
}a[N];
int main()
{
int i,n;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
ll ans=4e18+5;
a[n+1]=a[1];
a[n+2]=a[2];
for(i=1;i<=n;i++)
{
ans=min(ans,mianji(a[i+1].x-a[i].x,a[i+1].y-a[i].y,a[i+2].x-a[i].x,a[i+2].y-a[i].y));
}
cout<<ans<<endl;
return 0;
}