Cod sursa(job #1969541)

Utilizator rares1012Rares Cautis rares1012 Data 18 aprilie 2017 15:17:20
Problema Tribute Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#include <math.h>

int x[50000],y[50000];

int compare(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}

int main()
{
    int n,l,w,i,sus,jos=0,st=0,dr=0,r,p,njos,s=0,pozx,pozy,ndr;
    FILE*fi,*fo;
    fi=fopen("tribute.in","r");
    fo=fopen("tribute.out","w");
    fscanf(fi,"%d%d%d",&n,&l,&w);
    for(i=0;i<n;i++){
        fscanf(fi,"%d%d",&x[i],&y[i]);
    }
    qsort(x,n,sizeof(int),compare);
    qsort(y,n,sizeof(int),compare);
    for(i=0;i<n;i++)
    {
        if(x[i]>l)
            jos++;
    }
    for(i=0;i<n;i++)
    {
        if(y[i]>l)
            dr++;
    }
    p=1<<16;
    r=0;
    while(p>0){
        if(r+p<50001)
        {
            i=r+p;
            njos=jos;
            sus=0;
            for(i=0;i<n;i++)
            {
                if(x[i]<r+p){
                    sus++;
                }
                else if(x[i]<=r+p+l && x[i]>=r+p)
                {
                    njos--;
                }
            }
            if(sus<njos){
                r+=p;
                jos=njos;
            }
        }
        p/=2;
    }
    pozx=r+1;
    p=1<<16;
    r=0;
    while(p>0){
        if(r+p<50001)
        {
            i=r+p;
            ndr=dr;
            st=0;
            for(i=0;i<n;i++)
            {
                if(y[i]<r+p){
                    st++;
                }
                else if(y[i]<=r+p+w && y[i]>=r+p)
                {
                    ndr--;
                }
            }
            if(st<ndr){
                r+=p;
                dr=ndr;
            }
        }
        p/=2;
    }
    pozy=r+1;
    for(i=0;i<n;i++)
    {
        if(x[i]<pozx)
            s+=pozx-x[i];
        else if(x[i]>pozx+l)
            s+=x[i]-pozx-l;
        if(y[i]<pozy)
            s+=pozy-y[i];
        else if(y[i]>pozy+w)
            s+=y[i]-pozy-w;
    }
    fprintf(fo,"%d",s);
    fclose(fi);
    fclose(fo);
    return 0;
}