Container Polygon

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define SWAP(a,b) {int t=a;a=b;b=t;}
#define M 100000

using namespace std;

struct _tuple {
    int pos;
    int h;

};

int n;
int ar=0;
_tuple A[M];


void input()
{
    //freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d %d",&A[i].pos,&A[i].h);
    }
}

void print() {
    printf("%d",ar);
    puts("");
}

bool sf(_tuple a,_tuple b) {
    return a.h<b.h;
}


int main()
{
    input();
    sort(A,A+n,sf);
    int j=n-2;
    int lx;
    int rx;
    int max_h;
    lx=A[n-1].pos;
    rx=A[n-1].pos+1;
    //printf("%d,%d\n",lx,rx);
    ar+=A[n-1].h;
    while(j>=0){
        if(A[j].pos<=lx){
            ar+= A[j].h*(lx-A[j].pos);
            //printf("%d*(%d-%d)=%d\n", A[j].h,lx,A[j].pos,ar);
            lx=A[j].pos;

        }
        if(A[j].pos>=rx){
            ar+= A[j].h*(A[j].pos-rx+1);
            //printf("%d*(%d-%d)=%d\n", A[j].h,A[j].pos,rx,ar);
            rx=A[j].pos+1;

        }
        j--;
    }
    print();
    return 0;
}