Pagini recente » Cod sursa (job #2251054) | Cod sursa (job #2249877) | Cod sursa (job #423483) | Cod sursa (job #536156) | Cod sursa (job #2140734)
#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;
}