Cod sursa(job #470444)

Utilizator johnny2008Diaconu Ion johnny2008 Data 13 iulie 2010 20:16:56
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
#define INF 100000
#define NMAX 50666

using namespace std;
 
int X[NMAX], Y[NMAX], N;
 
int dist(int v[NMAX], int l, int &p)
{
    int cs = 0, cd, d = 0, i = 1, a, b, j, dmin;
 
    a = v[cs];
    b = v[cs]+l;
    while (v[i] < b) i++;
 
    for (j = i; j < N; j++) d += (v[j]-b);
    dmin = d;
    p = a;
 
    cs = 1;
    cd = i;
 
    while (cd < N)
    {
            if (v[cs]-a < v[cd]-b)
            {
                    d = d+cs*(v[cs]-a)-(N-cd)*(v[cs]-a);
                    a = v[cs];
                    b = a+l;
                    cs++;
            }
            else
            {
                    d = d+cs*(v[cd]-b)-(N-cd)*(v[cd]-b);
                    b = v[cd];
                    a = b-l;
                    cd++;
            }
            if (dmin > d) dmin = d, p = a;
    }
 
    return dmin;

}
 
int main()
{
    int i, l, c, s = 0, lx, ly;
 
    ifstream f("tribute.in");
    ofstream g("tribute.out");
     
    f>>N>>lx>>ly;
 
    for(i = 0; i < N; i++) f>>X[i]>>Y[i];
    sort(&X[0], &X[N]); X[N] = INF;
    sort(&Y[0], &Y[N]); Y[N] = INF;
 
    s+=dist(X, lx, l);
    
    s+=dist(Y, ly, c);
 
     
    g<<s;
 
    return 0;
 
}