Cod sursa(job #2072818)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 22 noiembrie 2017 11:42:05
Problema Rays Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct interval
{
    int x, y1, y2;
}; interval aux;
vector <interval> st, dr;
bool cmp(interval a, interval b)
{
    return a.y2 * b.x < b.y2 * a.x;
}
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;
            st.push_back(aux);
        }
        else {
            aux.x = x;
            dr.push_back(aux);
        }
    }
    if (st.size() > 0)
    {
        last = 0; ++ans;
        sort (st.begin(), st.end(), cmp);
        for (int i = 1; i < st.size(); ++i)
            if ((long long) st[i].y1 * st[last].x > (long long) st[last].y2 * st[i].x)
            {
                last = i;
                ++ans;
            }
    }
    if (dr.size() > 0)
    {
        last = 0; ++ans;
        sort (dr.begin(), dr.end(), cmp);
        for (int i = 1; i < dr.size(); ++i)
            if ((long long) dr[i].y1 * dr[last].x > (long long) dr[last].y2 * dr[i].x)
            {
                last = i;
                ++ans;
            }
    }
    printf("%d\n", ans);
    return 0;
}