#include #include using namespace std; #define MAXN 100000 // y-ové súradnice koncov čiar, usporiadané zostupne int Y[MAXN]; // body na vstupe pair body[MAXN]; int main() { int N, x, y, poc = 0; cin >> N; for (int i = 0; i < N; i++) { cin >> x >> y; // otočiť súradnice o 45 stupňov body[i] = make_pair(x+y,x-y); } // utriediť podľa x (pre rovnaké x podľa y) sort(body,body+N); for (int i = 0; i < N; i++) { // binárnym vyhľadávaním nájsť najvyšší koniec, // ktorý je nižšie ako súradnica y int pos = lower_bound(Y,Y+poc,-body[i].second)-Y; // ak taký nie je, vytvoriť nový if (pos == poc) poc++; // predĺžiť nájdený koniec čiary Y[pos] = -body[i].second; } cout << poc << endl; return 0; }