Cod sursa(job #489664)

Utilizator andreea1coolBobu Andreea andreea1cool Data 3 octombrie 2010 11:01:09
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,i,j,k,ok,smin,dx,dy,sx,sy,v1[50010],v2[50010],min1,min2,xmin=99999,xmax=-1,ymin=99999,ymax=-1,solx1,solx2,soly1,soly2;

int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d%d%d",&n,&dx,&dy);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&m,&j);
        v1[m]++;
        v2[j]++;
        if(m<xmin)xmin=m;
        if(m>xmax)xmax=m;
        if(j<ymin)ymin=j;
        if(j>ymax)ymax=j;
    }

    for(i=xmin+dx+1;i<=xmax;i++)
    {
        solx1+=v1[i];
        soly1+=v1[i]*(i-xmin-dx);
    }
    min1=soly1;
    for(i=xmin+1;i<=xmax-dx;i++)
    {
        soly1-=solx1;
        solx1-=v1[i+dx];
        solx2+=v1[i-1];
        soly2+=solx2;
        if(soly1+soly2<min1)min1=soly1+soly2;
    }
    soly1=0; soly2=0;
    solx1=0; solx2=0;
    for(i=ymin+dy+1;i<=ymax;i++)
    {
        solx1+=v2[i];
        soly1+=v2[i]*(i-ymin-dy);
    }
    min2=soly1;
    for(i=ymin+1;i<=ymax-dy;i++)
    {
        soly1-=solx1;
        solx1-=v2[i+dy];
        solx2+=v2[i-1];
        soly2+=solx2;
        if(soly1+soly2<min2)min2=soly1+soly2;
    }

    printf("%d",min1+min2);

    return 0;
    }