Cod sursa(job #2140734)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 23 februarie 2018 20:17:12
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <algorithm>
#include <stdlib.h>
#define nmax 50005
using namespace std;
fstream f1("tribute.in", ios::in);
fstream f2("tribute.out", ios::out);
int n, dx, dy, sumax, sumay, rez, xmax, ymax;
struct obi
{
  int x, y;
}v[nmax];
///pt intervalul curent [i, i+dx] sumax= suma minima a distantelor pe axa Ox
///pt intervalul curent [i, i+dy] sumay= suma minima a distantelor pe axa Oy
bool cmp1(obi a, obi b)
{
    return a.x< b.x;
}
bool cmp2(obi a, obi b)
{
    return a.y< b.y;
}
void citire()
{
    int i, stx=1, drx=1, sty=1, dry=1, mini;
    f1>>n>>dx>>dy;
    for(i=1; i<=n; i++) ///initial se ia intervalul [0, dx] [0, dy]
       {
           f1>>v[i].x>>v[i].y; if(xmax< v[i].x) xmax=v[i].x; if(ymax< v[i].y) ymax=v[i].y;
           if(v[i].x> dx) sumax+=(v[i].x- dx);
           if(v[i].y> dy) sumay+=(v[i].y- dy);
       }

    sort(v+1, v+n+1, cmp1);
    mini=sumax;
    for(i=1; i<=xmax-dx+1; i++)
    {
        ///[i, i+dx]
        while((stx<=n)&&(v[stx].x< i)) stx++; ///stx= indicele primului punct din interval
        while((drx<=n)&&(v[drx].x< i+dx)) drx++; ///drx= indicele primului punct din afara intervalului
        sumax+=(stx-1);   ///te indepartezi cu o unitate de punctele din afara intervalului din stanga
        sumax-=(n-drx+1); ///te apropii cu o unitate de punctele din afara intervalului din dreapta
        if(mini> sumax) mini=sumax;
    }
    rez+=mini;


    sort(v+1, v+n+1, cmp2);
    mini=sumay;
    for(i=1; i<=ymax-dy+1; i++)
    {
        ///[i, i+dx]
        while((sty<=n)&&(v[sty].y< i)) sty++;
        while((dry<=n)&&(v[dry].y< i+dy)) dry++;
        sumay+=(sty-1);
        sumay-=(n-dry+1);
        if(mini> sumay) mini=sumay;
    }
    rez+=mini;
}
int main()
{
    citire();
    f2<<rez;
    return 0;
}