Cod sursa(job #3186385)

Utilizator divadddDavid Curca divaddd Data 22 decembrie 2023 21:02:44
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;

ifstream fin("rays.in");
ofstream fout("rays.out");

struct Fractie{
    int a, b;
    Fractie(){}
    Fractie(int _a, int _b){
        a = _a;
        b = _b;
    }
    bool operator <= (const Fractie &aux) const{
        return (a * aux.b) <= (b * aux.a);
    }
    bool operator < (const Fractie &aux) const{
        return (*this <= aux);
    }
};
vector<pair<Fractie, Fractie>> pos, neg;

signed main()
{
    fin >> n;
    for(int i = 1; i <= n; i++){
        int x, y1, y2;
        fin >> x >> y1 >> y2;
        Fractie l(y1, x), r(y2, x);
        if(!(l <= r)){
            swap(l, r);
        }
        if(x >= 0){
            pos.push_back({l, r});
        }else{
            neg.push_back({l, r});
        }
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    int ans = 1;
    pair<Fractie, Fractie> acumm = pos[0];
    for(int i = 1; i < pos.size(); i++){
        if(pos[i].first <= acumm.second){
            if(pos[i].second <= acumm.second){
                acumm.second = pos[i].second;
            }
        }else{
            ans++;
            acumm = pos[i];
        }
    }
    ans++;
    acumm = neg[0];
    for(int i = 1; i < neg.size(); i++){
        if(neg[i].first <= acumm.second){
            if(neg[i].second <= acumm.second){
                acumm.second = neg[i].second;
            }
        }else{
            ans++;
            acumm = neg[i];
        }
    }
    fout << ans;
    return 0;
}