Cod sursa(job #2072802)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 22 noiembrie 2017 11:30:31
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1.e-14;
struct interval
{
    int x, y1, y2;
    double m1, m2;
}; interval aux;
vector <interval> st, dr;
bool cmp(interval a, interval b)
{
    return a.m2 < b.m2;
}
int main()
{
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);
    int n, x, y1, y2, ans = 0;
    double last;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d %d", &x, &y1, &y2);
        if (y1 > y2)
            swap(y1, y2);
        aux.y1 = y1;
        aux.y2 = y2;
        if (x < 0) {
            aux.x = -x;
            aux.m1 = (double) y1 / -x;
            aux.m2 = (double) y2 / -x;
            st.push_back(aux);
        }
        else {
            aux.x = x;
            aux.m1 = (double) y1 / x;
            aux.m2 = (double) y2 / x;
            dr.push_back(aux);
        }
    }
    if (st.size() > 0)
    {
        last = st[0].m2; ++ans;
        sort (st.begin(), st.end(), cmp);
        for (int i = 1; i < st.size(); ++i)
            if (st[i].m1 - last > eps)
            {
                last = st[i].m2;
                ++ans;
            }
    }
    if (dr.size() > 0)
    {
        last = dr[0].m2; ++ans;
        sort (dr.begin(), dr.end(), cmp);
        for (int i = 1; i < dr.size(); ++i)
            if (dr[i].m1 - last > eps)
            {
                last = dr[i].m2;
                ++ans;
            }
    }
    printf("%d\n", ans);
    return 0;
}