Cod sursa(job #230063)

Utilizator katakunaCazacu Alexandru katakuna Data 12 decembrie 2008 21:19:27
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include <algorithm>
#define INF 1<<30 ;
using namespace std;

int rez,Min,a,b,i,S,n,dx,dy,maxx,maxy,x[50111],y[50111],vix[50111],viy[50111];


int main(){

FILE *f=fopen("tribute.in","r");
fscanf(f,"%d %d %d",&n,&dx,&dy);
maxx=maxy=-1;

  for(i=1;i<=n;i++){
  fscanf(f,"%d %d",&x[i],&y[i]);
  vix[x[i]]++;

    if(x[i]>maxx)
    maxx=x[i];
    
  viy[y[i]]++;

    if(y[i]>maxy)
    maxy=y[i];
  }

fclose(f);


sort(x+1,x+1+n);
sort(y+1,y+1+n);

  for(i=1;i<=maxx;i++)
  vix[i]+=vix[i-1];

int q=dx+x[1];

   for(i=1;i<=n;i++){
     if(x[i]>q)
     S+=x[i]-q;
   }

Min=INF;

i=x[1]+1;

    for(i=x[1]+1;i+dx<=maxx;i++){
    a=i;
    b=i+dx;
    S+=vix[a-1];
    S-=(n - vix[ (b-1) ]);
//    q=1;
       if(S<Min)
       Min=S;
    }

rez=Min;
Min=INF;

  for(i=1;i<=maxy;i++)
  viy[i]+=viy[i-1];

q=dy+y[1];
S=0;
   for(i=1;i<=n;i++){
     if(y[i]>q)
     S+=y[i]-q;
   }

Min=INF;

    for(i=y[1]+1;i+dy<=maxy;i++){
    a=i;
    b=i+dy;
    S+=viy[a-1];
    S-=(n - viy[ (b-1) ]);
//    q=1;
       if(S<Min)
       Min=S;
    }


FILE *g=fopen("tribute.out","w");
rez+=Min;
   fprintf(g,"%d",rez);
fclose(g);

return 0;
}