2021-6-5 ACM-SDU 集训题解

总体来说，这次的题目相对简单，选择几个稍微值得注意的题写题解

B

原题传送门：Problem - B - Codeforces

题意：有一个严格的凸多边形，求此凸多边形的内接三角形的面积的最小值。

解题思路：不难想到，对一个凸多边形，若其内接三角形面积取到最小，那么这个三角形一定与原多边形有两条公共边。（证明？？不存在的）

（其实证明的话自己画下图就能知道啦！）

实现：预处理一下数据（由于点是按照顺序给的，所以我们只需要把头两个节点放在数组后即可）

取连续三个点当作三角形的顶点，算三角形的面积，取所有的面积的最大值为ans

源码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
ll n,xx[maxn],yy[maxn];
ll res=4e18;//由于求最小值，所以初始化较大
ll getres(ll x1,ll y1,ll x2,ll y2){
    return abs(x1*y2-x2*y1);//求叉乘
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>xx[i]>>yy[i];
    }

    xx[n]=xx[0];yy[n]=yy[0];//数据的预处理
    xx[n+1]=xx[1];yy[n+1]=yy[1];

    for(int i=0;i<n;++i){//计算以i,i+1,i+2为顶点的三角形面积
        ll tempx1=xx[i+1]-xx[i],tempy1=yy[i+1]-yy[i];
        ll tempx2=xx[i+2]-xx[i],tempy2=yy[i+2]-yy[i];
        res=min(res,getres(tempx1,tempy1,tempx2,tempy2));
    }

    cout<<res<<endl;

}