Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define NMAX 100005
- #define ll long long int
- using namespace std;
- struct linie{
- int index;
- int start;
- int x, y;
- };
- linie L[NMAX];
- ll valori[NMAX];
- int criteriu(linie a, linie b){
- if(a.start > b.start)
- return 1;
- return 0;
- }
- int compar(ll a, ll b){
- if( (L[a].y - L[a].start)*L[b].x > (L[b].y - L[b].start)*L[a].x)
- return 1;
- return 0;
- }
- vector<ll> tail;
- ll tests, nt, n, Start, X, Y, i;
- void cautNr(ll nrCautat){
- ll st = -1, dr = tail.size(), mid;
- while(dr - st > 1){
- mid = (st+dr)/2;
- if(compar(tail[mid], nrCautat) == 1)
- st = mid;
- else
- dr = mid;
- }
- if(tail[st] > nrCautat)
- tail[st] = nrCautat;
- else if(tail[dr] > nrCautat)
- tail[dr] = nrCautat;
- }
- ll a;
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin >> tests;
- for(nt=1; nt<=tests; nt++){
- cin >> n;
- for(i=1; i<=n; i++){
- cin >> Start >> X >> Y;
- L[i].index = i;
- L[i].start = Start;
- L[i].x = X;
- L[i].y = Y;
- }
- sort(L+1, L+n+1, criteriu);
- for(i=1; i<=n; ++i){
- if(tail.size() == 0)
- tail.push_back(i);
- else if(compar(i, tail[0]))
- tail[0] = i;
- else if(compar(tail[tail.size()-1], i) == 1)
- tail.push_back(i);
- else
- cautNr(i);
- }
- cout << tail.size() << '\n';
- tail.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement