凸包和凸组合例题-526互联

https://codeforces.com/gym/467720/attachments M题
网上博客 https://blog.csdn.net/weixin_34284188/article/details/94669467
我们最终线性组合的点一定会落在凸包内部，我们的答案就是凸包的上，右边界的点，包括端点，也包括凸包边上的点
求凸包边上的点的横纵坐标积的最大值，是列出二元一次方程，求最值。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define x first
#define y second
typedef pair<double,double> PDD;
const int N  =3e4+10;
const double eps = 1e-8;
int stk[N],top;

PDD q[N];
PDD operator -(PDD a,PDD b)
{
    return {a.x- b.x,a.y-b.y};
}
double cross(PDD a,PDD b)
{
    return a.x*b.y - a.y*b.x;
}
double area(PDD a,PDD b,PDD c)
{
    return cross(b-a,c-a);
}
int sign(double x)
{
    if(fabs(x)<eps) return 0;
    if(x>0) return 1;
    return -1;
}
int n;
int C;

//求上凸壳边上的最值
double cal(PDD u,PDD v)
{
    double A = (u.x - v.x) * (u.y - v.y);
    double B = (u.x - v.x) * v.y + (u.y - v.y) * v.x;
    double C = v.x * v.y;
    double x = -0.5 * B / A;
    if (sign(x - 0.0) <= 0)
        return 0;
    else
        x = min(x, 1.0);
    return (A * x + B) * x + C;

}
double ans = 0.0;
void andrew()
{
    sort(q,q+n);
    for(int i= 0;i<n;i++)
    {
        while(top>=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))>0) top--;
        stk[++top] = i;
    }
    for(int i = 1;i<top;i++)
    ans = max(ans,cal(q[stk[i]],q[stk[i+1]]));
}
int main()
{
    cin>>n>>C;
    for(int i = 0;i<n;i++)
    {
        double c,h,p;
        scanf("%lf%lf%lf",&c,&h,&p);
        q[i] = {(double)h/c*C,(double)p/c*C};
        ans = max(ans,q[i].x*q[i].y);
    }
    andrew();
    printf("%.2lf\n",ans);
    
    return 0;
}

凸包

例题