Gym - 101755B Minimal Area 叉积计算三角形面积

题目链接

题意：

按逆时针的顺序给出一个凸多边形的n个顶点，求一个顶点都在凸多边形上，面积最小的三角形，输出三角形面积的二倍

思路：

面积最小的三角形一定是三个相连的顶点的面积，按顺序遍历每三个相连的顶点，找最小值，

求三角形面积用叉积公式：

a(x1,y1),b(x2,y2),c(x3,y3);

S=0.5*abs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1));

代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2e5+5;
int n;

struct node {
 long double x,y;
} a[maxn];

ll chk(node a,node b,node c) {
 ll x1=a.x;
 ll x3=c.x;
 ll x2=b.x;
 ll y1=a.y;
 ll y3=c.y;
 ll y2=b.y;
 return abs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1));

}

int main() {
 cin>>n;
 for(int i=1; i<=n; i++) {
  cin>>a[i].x>>a[i].y;
 }
 a[n+1]=a[1];
 a[n+2]=a[2];
 n+=2;
 ll ma=0x3f3f3f3f3f3f3f3f;
 for(int i=3; i<=n; i++) {
  ma=min(ma,chk(a[i-2],a[i-1],a[i]));
 }
 printf("%lld\n",ma);
 return 0;
}