Cod sursa(job #8249)

Utilizator mockeBarca Cristian Mihai mocke Data 23 ianuarie 2007 23:17:40
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
//90p

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MIN(a, b) ( (a) < (b) ? (a) : (b) )
#define MAX(a, b) ( (a) > (b) ? (a) : (b) )
#define ABS(a) ( (a) < (0) ? (-(a)) : (a) )
#define MAXC 50001
#define NMAX 60012

int isX[NMAX], isY[NMAX], stX[NMAX], drX[NMAX], stY[NMAX], drY[NMAX];
int N, i;
int Px, Py, dx, dy, x, y, maxX, minX, maxY, minY;
long long Dpx, Dpy;

int cordMan(int isC[], int stC[], int drC[], int a, int b, int d)
{

   int i, dif = MAXC + 1, pst, pdr, pC = a;

   if (a + d >= b) { dif = 0; return pC; }

   for (i = a; i <= b; i++)
   {
          if (isC[i])
          {
             pst =  (i - 1 >= 0) ? stC[i-1] : 0;
             pdr =  (i + d < MAXC) ? drC[i+d+1] : 0;

             if ( dif > ABS(pst - pdr) )
                        dif = ABS(pst - pdr), pC = i;
          }
   }

   for (i = a; i <= b; i++)
   {
          if (isC[i])
          {
             pst =  (i - d > 0) ? stC[i-d-1] : 0;
             pdr =  (i + 1 <= MAXC) ? drC[i+1] : 0;

             if ( dif > ABS(pst - pdr) )
                        dif = ABS(pst - pdr), pC = i - d;
          }
   }

   return pC;
}

long long distMan(int isC[], int a, int b, int P, int d)
{
     long long dist = 0;
     int i;

     for (i = a; i <= b; i++)
        if ( isC[i] && (i < P || P + d < i) )
            dist += (long long)MAX(P-i, i - P - d) * isC[i];

     return dist;
}

int main()
{
     freopen("tribute.in", "r", stdin);
     freopen("tribute.out", "w", stdout);

     scanf("%d %d %d", &N, &dx, &dy);

     minX = minY = MAXC + 1;

     for (i = 1; i <= N; i++)
     {
          scanf("%d %d", &x, &y);

          minX = MIN(minX, x), minY = MIN(minY, y);
          maxX = MAX(maxX, x), maxY = MAX(maxY, y);

          isX[x]++, stX[x]++, drX[x]++;
          isY[y]++, stY[y]++, drY[y]++;
     }

     for (i = minX + 1; i <= maxX; i++) stX[i] = stX[i - 1] + stX[i];

     for (i = minY + 1; i <= maxY; i++) stY[i] = stY[i - 1] + stY[i];

     for (i = maxX - 1; i >= minX; i--) drX[i] = drX[i + 1] + drX[i];

     for (i = maxY - 1; i >= minY; i--) drY[i] = drY[i + 1] + drY[i];


     Px = cordMan(isX, stX, drX, minX, maxX, dx);
     Py = cordMan(isY, stY, drY, minY, maxY, dy);

     Dpx = distMan(isX, minX, maxX, Px, dx);
     Dpy = distMan(isY, minY, maxY, Py, dy);


     printf("%lld\n", (long long)Dpx + Dpy);


     fclose(stdin);
     fclose(stdout);

     return 0;
}