Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct linie
  4. {
  5. int x, y, nr;
  6. };
  7. linie v[105];
  8. vector<int> smax;
  9. bool cmp(linie a, linie b)
  10. {
  11. return a.x < b.x;
  12. }
  13. bool cmp2(linie a, linie b)
  14. {
  15. return a.y < b.y;
  16. }
  17. int n, a[105];
  18. int main()
  19. {
  20. cin >> n;
  21. for(int i=1; i<=n; i++)
  22. cin >> v[i].x >> v[i].y;
  23. sort(v+1, v+n+1, cmp);
  24. for(int i=1; i<=n; i++)
  25. v[i].nr = i;
  26. int nr = 0;
  27. sort(v+1, v+1+n, cmp2);
  28. for(int i=1; i<=n; i++)
  29. a[++nr] = v[i].nr;
  30. for(int i=1; i<=n; i++)
  31. if(smax.empty() || a[i] >= smax.back())
  32. smax.push_back(a[i]);
  33. else
  34. {
  35. vector<int>::iterator it = upper_bound(smax.begin(), smax.end(), a[i]);
  36. *it = a[i];
  37. }
  38. cout << n - smax.size();
  39. return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement