Pagini recente » Cod sursa (job #2710735) | Cod sursa (job #524712) | Cod sursa (job #2259772) | Cod sursa (job #3131152) | Cod sursa (job #2353988)
#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;
}