Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define NMAX 100005
  3. #define ll long long int
  4.  
  5. using namespace std;
  6.  
  7. struct linie{
  8. int index;
  9. int start;
  10. int x, y;
  11. };
  12. linie L[NMAX];
  13. ll valori[NMAX];
  14. int criteriu(linie a, linie b){
  15. if(a.start > b.start)
  16. return 1;
  17. return 0;
  18. }
  19. int compar(ll a, ll b){
  20. if( (L[a].y - L[a].start)*L[b].x > (L[b].y - L[b].start)*L[a].x)
  21. return 1;
  22. return 0;
  23. }
  24. vector<ll> tail;
  25. ll tests, nt, n, Start, X, Y, i;
  26. void cautNr(ll nrCautat){
  27. ll st = -1, dr = tail.size(), mid;
  28. while(dr - st > 1){
  29. mid = (st+dr)/2;
  30. if(compar(tail[mid], nrCautat) == 1)
  31. st = mid;
  32. else
  33. dr = mid;
  34. }
  35. if(tail[st] > nrCautat)
  36. tail[st] = nrCautat;
  37. else if(tail[dr] > nrCautat)
  38. tail[dr] = nrCautat;
  39. }
  40. ll a;
  41.  
  42. int main()
  43. {
  44. ios_base::sync_with_stdio(false);
  45. cin >> tests;
  46. for(nt=1; nt<=tests; nt++){
  47. cin >> n;
  48. for(i=1; i<=n; i++){
  49. cin >> Start >> X >> Y;
  50. L[i].index = i;
  51. L[i].start = Start;
  52. L[i].x = X;
  53. L[i].y = Y;
  54. }
  55. sort(L+1, L+n+1, criteriu);
  56.  
  57. for(i=1; i<=n; ++i){
  58. if(tail.size() == 0)
  59. tail.push_back(i);
  60. else if(compar(i, tail[0]))
  61. tail[0] = i;
  62. else if(compar(tail[tail.size()-1], i) == 1)
  63. tail.push_back(i);
  64. else
  65. cautNr(i);
  66. }
  67. cout << tail.size() << '\n';
  68. tail.clear();
  69. }
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement