提交时间:2021-12-14 19:21:32

运行 ID: 35333

#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define gc getchar() #define ll long long using namespace std; const int N=5e4+10; inline void qr(ll &x) { x=0;int f=1;char c=gc; while(c<'0'||c>'9')c=gc; while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;} x*=f; } void qw(ll x) { if(x/10)qw(x/10); putchar(x%10+48); } struct node { ll x,y; }a[N]; bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;} ll f[N];int b[N],q[N],l,r; inline double calc(int j,int k){return (f[j]-f[k])/(double)(a[b[k+1]].y-a[b[j+1]].y);} int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++)qr(a[i].x),qr(a[i].y); sort(a+1,a+n+1,cmp); int tot=0; for(int i=1;i<=n;i++) { while(tot&&a[b[tot]].y<=a[i].y)--tot; b[++tot]=i; } l=1;r=1;q[1]=0; for(int i=1;i<=tot;i++) { while(l<r&&calc(q[l],q[l+1])<=1.0*a[b[i]].x)++l; f[i]=f[q[l]]+a[b[i]].x*a[b[q[l]+1]].y; while(l<r&&calc(q[r],i)<=calc(q[r-1],q[r]))--r; q[++r]=i; } qw(f[tot]);puts(""); return 0; }