Cod sursa(job #2012280)

Utilizator amaliarebAmalia Rebegea amaliareb Data 18 august 2017 14:10:22
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
struct miau{int x,y;} v[50005];
int n,i,j,X,Y,hdist,vdist,dx,dy,minhdist,minvdist,cresc, descresc,l,r;
ifstream f("tribute.in");
ofstream g("tribute.out");

bool cmpx(miau a, miau b)
{
    return a.x<b.x;
}

bool cmpy(miau a, miau b)
{
    return a.y<b.y;
}

int main()
{
    f>>n>>dx>>dy;
    for(i=1;i<=n;i++) f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmpx);
    X=0; Y=0; cresc=0; descresc=0;
    for(i=1;i<=n;i++)
        if(v[i].x<=X) hdist+=X-v[i].x, cresc++;
        else if(v[i].x>X+dx) hdist+=v[i].x-X-dx, descresc++;
    minhdist=hdist;
    l=1; r=1;
    while(v[l].x<=X && l<=n) l++;
    while(v[r].x<X+dx && r<=n) r++;
    for(i=1;i<=50000;i++)
    {
        X++;
        hdist+=cresc;
        hdist-=descresc;
        if(hdist<minhdist) minhdist=hdist;
        while(l<=n && v[l].x==X) l++, cresc++;
        while(r<=n && v[r].x==X+dx) r++, descresc--;
    }
    sort(v+1,v+n+1,cmpy);
    cresc=0; descresc=0;
    for(i=1;i<=n;i++)
        if(v[i].y<=Y) vdist+=Y-v[i].y, cresc++;
        else if(v[i].y>Y+dy) vdist+=v[i].y-Y-dy, descresc++;
    minvdist=vdist;
    l=1;r=1;
    while(v[l].y<=Y && l<=n) l++;
    while(v[r].y<Y+dy && r<=n) r++;
    for(i=1;i<=50000;i++)
    {
        Y++;
        vdist+=cresc;
        vdist-=descresc;
        if(vdist<minvdist) minvdist=vdist;
        while(l<=n && v[l].y==Y) l++, cresc++;
        while(r<=n && v[r].y==Y+dy) r++, descresc--;
    }
    g<<minhdist+minvdist<<'\n';
    return 0;
}