Cod sursa(job #2240352)

Utilizator giotoPopescu Ioan gioto Data 13 septembrie 2018 09:54:46
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

int n;
vector <pair <double, double> > st;
vector <pair <double, double> > dr;
int main()
{
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);

    scanf("%d", &n);
    int x, y1, y2;
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d%d", &x, &y1, &y2);
        if(y1 > y2) swap(y1, y2);
        if(x > 0) st.push_back({1.0 * y1 / x, 1.0 * y2 / x});
        else dr.push_back({-(1.0 * y1 / x), -(1.0 * y2 / x)});
    }

    sort(st.begin(), st.end());
    int Sol = 0;
    double R = st.begin()->first - 1;
    for(auto it : st){
        if(it.first <= R) R = min(it.second, R);
        else{
            ++Sol;
            R = it.second;
        }
    }

    sort(dr.begin(), dr.end());
    R = dr.begin()->first - 1;
    for(auto it : dr){
        if(it.first <= R) R = min(it.second, R);
        else{
            ++Sol;
            R = it.second;
        }
    }

    printf("%d", Sol);

    return 0;
}