Pagini recente » Cod sursa (job #2964820) | Cod sursa (job #1571301) | Cod sursa (job #1195468) | Cod sursa (job #2514030) | Cod sursa (job #2875401)
#include <bits/stdc++.h>
#define COORDMAX 50005
using namespace std;
/*******************************/
// INPUT / OUTPUT
ifstream f("tribute.in");
ofstream g("tribute.out");
/*******************************/
/// GLOBAL DECLARATIONS
int N, DX, DY;
int finX, finY;
int ox, oy;
struct Point
{
int x, y;
} point;
vector <Point> points;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
f >> N >> DX >> DY;
int x, y;
for (int i = 0 ; i < N ; ++ i)
{
f >> x >> y;
points.push_back({x, y});
}
}
///-------------------------------------
bool compX(const Point &a, const Point &b)
{
if (a.x == b.x)
{
return a.y < b.y;
}
return a.x < b.x;
}
///-------------------------------------
bool compY(const Point &a, const Point &b)
{
if (a.y == b.y)
{
return a.x < b.x;
}
return a.y < b.y;
}
///-------------------------------------
inline void GetOX()
{
int x1 = 0, x2 = DX;
int sumSt = 0, sumDr = 0, pointsInside = 0, pointsSt = 0, pointsDr = 0;
sort(points.begin(), points.end(), compX);
for (int i = 0 ; i < N ; ++ i)
{
point = points[i];
if (point.x < x1)
{
sumSt += (x1 - point.x);
pointsSt ++;
}
else
{
if (point.x > x2)
{
sumDr += point.x - x2;
pointsDr ++;
}
else
{
pointsInside ++;
}
}
}
ox = sumSt + sumDr;
x1 ++, x2 ++;
while (x2 <= COORDMAX)
{
sumDr -= pointsDr;
while (points[pointsSt].x == x1 - 1)
{
pointsSt ++;
}
while (points[pointsSt + pointsInside].x == x2)
{
pointsInside ++;
pointsDr --;
}
sumSt += pointsSt;
if (ox > sumSt + sumDr)
{
ox = sumSt + sumDr;
finX = x1;
}
x1 ++, x2 ++;
}
}
///-------------------------------------
inline void GetOY()
{
int y1 = 0, y2 = DY;
int sumJos = 0, sumSus = 0, pointsInside = 0, pointsJos = 0, pointsSus = 0;
sort(points.begin(), points.end(), compY);
for (int i = 0 ; i < N ; ++ i)
{
point = points[i];
if (point.y < y1)
{
sumSus += (y1 - point.y);
pointsSus ++;
}
else
{
if (point.y > y2)
{
sumJos += point.y - y2;
pointsJos ++;
}
else
{
pointsInside ++;
}
}
}
oy = sumSus + sumJos;
y1 ++, y2 ++;
while (y2 <= COORDMAX)
{
sumJos -= pointsJos;
while (points[pointsSus].y == y1 - 1)
{
pointsSus ++;
}
while (points[pointsSus + pointsInside].y == y2)
{
pointsInside ++;
pointsJos --;
}
sumSus += pointsSus;
if (oy > sumSus + sumJos)
{
oy = sumSus + sumJos;
finY = y1;
}
y1 ++, y2 ++;
}
}
///-------------------------------------
inline void Solution()
{
GetOX();
GetOY();
}
///-------------------------------------
inline void Output()
{
g << ox + oy;
}
///-------------------------------------
int main()
{
ReadInput();
Solution();
Output();
return 0;
}