Cod sursa(job #4017)

Utilizator zombie_testeala bala portocala si mandarina zombie_teste Data 30 decembrie 2006 00:32:09
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb

#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 50002
#define NMAX 50012

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

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

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

   if (a + d >= b) return a;

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

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

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

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

   return pC;
}

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

     for (i = a; i <= b; i++)
        if (isC[i] && i < P || P + d < i)
            dist += MIN(ABS(P-i), ABS(P+d-i)) * 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;

     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 = 1; i <= MAXC; i++)
     {
          stX[i] = stX[i - 1] + stX[i];
          stY[i] = stY[i - 1] + stY[i];
     }

     for (i = MAXC - 1; i >= 0; i--)
     {
          drX[i] = drX[i + 1] + drX[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("%d\n", Dpx + Dpy);

     fclose(stdin);
     fclose(stdout);
     return 0;
}