Cod sursa(job #834538)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 14 decembrie 2012 17:04:46
Problema Tribute Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
using namespace std;

int n,dx,dy,x[50001],y[50001],s[50001],sy[50001],p=0,p2=0;
int maxi=INT_MAX;
int main()
{
    ifstream fin("tribute.in");
    ofstream fout("tribute.out");

    fin>>n>>dx>>dy;
    for(int i=1;i<=n;i++)
        fin>>x[i]>>y[i];
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);
    for(int i=x[1];i<=x[n]-dx;i++)
    {
        ++p;
        for(int j=1;j<=n;j++)
        {
            if(x[j]<i) s[p]+=(i-x[j]);
                else if(x[j]>i+dx) s[p]+=x[j]-i-dx;
        }
        if(s[p]>s[p-1] && p>1) break;
    }
    p2=0;
    for(int i=y[1];i<=y[n]-dy;i++)
    {
        ++p2;
        for(int j=1;j<=n;j++)
        {
            if(y[j]<i) sy[p2]+=(i-y[j]);
                else if(y[j]>i+dy) sy[p2]+=y[j]-i-dy;
        }
        if(s[p2]>s[p2-1] && p2>1) break;
    }
    for(int i=1;i<=p;i++)
        for(int j=1;j<=p2;j++)
        {
            if(s[i]+sy[j]<maxi) maxi=s[i]+sy[j];
        }
    fout<<maxi;
    return 0;
}