Cod sursa(job #2875407)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 21 martie 2022 16:44:04
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.61 kb
#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 ++;
            pointsInside --;
        }

        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 (pointsSus < N && points[pointsSus].y == y1 - 1)
        {
            pointsSus ++;
            pointsInside --;
        }

        while (pointsSus + pointsInside < N && 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;
}