Minimal Area 三角形面积

题目链接

http://codeforces.com/gym/101755/problem/B

题意

给你一个n个点的凸多边形，逆时针给出每个点的坐标。让你求出找的三角形的面积，三角形的三个角的坐标。

输出这个三角形面积的二倍。

题解

这三角形三个点的左边为（x1,y1）,(x2,y2),(x3,y3);

三角形面积的二倍等于下边这个行列式的值：

 

 最小的三角形的三个坐标点是这个多边形相邻的三个顶点。

枚举一下就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
typedef long long ll;
struct node{
    ll x,y;
}a[maxn];
ll area(node A,node B,node C){
    return A.x*B.y+B.x*C.y+C.x*A.y-B.x*A.y-C.x*B.y-C.y*A.x;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%lld%lld",&a[i].x,&a[i].y);
    ll res=9e18;
        for(int i=0;i<n-2;i++){
            ll x=area(a[i],a[i+1],a[i+2]);
            res=min(res,x);
        }
        ll x=area(a[n-2],a[n-1],a[0]);
        res=min(res,x);
         x=area(a[n-1],a[0],a[1]);
        res=min(res,x);
    printf("%lld\n",res);
    return 0;
}