Cod sursa(job #2353988)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 24 februarie 2019 19:31:24
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

ifstream fin("pachete.in");
ofstream fout("pachete.out");

struct oras{
    int x, y;
    long long distFromB;
}v[50005];

struct chestie{
    int x, y;
    long long curDist;
}rezs[50005];

pair <int, int> base;

inline bool cmp(oras a, oras b){
    return (a.distFromB <= b.distFromB);
}

void xSort(int poz){
    while(rezs[poz].curDist < rezs[poz - 1].curDist && poz >= 2){
        chestie aux = rezs[poz];
        rezs[poz] = rezs[poz - 1];
        rezs[poz - 1] = aux;
        --poz;
    }
}

int nrT = 0;
void updateRez(int poz){
    int st = 1;
    int dr = nrT;
    int pozX = -1;
    while(st <= dr){
        int mij = (st + dr) / 2;
        long long newD = 2 * (rezs[mij].curDist + (1LL * abs(rezs[mij].x - v[poz].x) + 1LL * abs(rezs[mij].y - v[poz].y)));
        if(newD <= 2 * v[poz].distFromB){
            pozX = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    if(pozX == -1){
        rezs[++nrT].x = v[poz].x;
        rezs[nrT].y = v[poz].y;
        rezs[nrT].curDist = v[poz].distFromB;
        xSort(nrT);

    }
    else {
        rezs[pozX].curDist += (1LL * abs(rezs[pozX].x - v[poz].x) + 1LL * abs(rezs[pozX].y - v[poz].y));
        rezs[pozX].x = v[poz].x;
        rezs[pozX].y = v[poz].y;
        xSort(pozX);
    }
}

int main()
{
    int n;
    fin >> n;

    fin >> base.first >> base.second;
    for(int i = 1; i <= n; ++i){
        int pozX, pozY;
        fin >> pozX >> pozY;

        v[i].x = pozX;
        v[i].y = pozY;
        v[i].distFromB = 1LL * abs(base.first - pozX) + 1LL * abs(base.second - pozY);
    }

    sort(v + 1, v + n + 1, cmp);

    int i = 1;
    while(i <= n){
        updateRez(i);
        ++i;
    }

    fout << nrT << '\n';
    return 0;
}