Cod sursa(job #1900887)

Utilizator antanaAntonia Boca antana Data 3 martie 2017 17:15:13
Problema Rays Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cmath>
#include <cstdio>
#include <algorithm>

#define MAXN 200001
#define EPS 1e-12

using namespace std;

struct lines{
    double left, right;

    bool operator < (const lines &aux) const {
        if(abs(left - aux.left) < EPS)
            return right < aux.right;
        return left < aux.left;
    }
} v[MAXN], now;

int n;

int main()
{
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);

    int segments = 1, i, x, y1, y2;

    scanf("%d", &n);

    for(i=1; i<=n; ++i) {
        scanf("%d%d%d", &x, &y1, &y2);
        v[i].left = atan2(y1, x);
        v[i].right = atan2(y2, x);

        if(v[i].right < v[i].left)
            swap(v[i].left, v[i].right); }

    sort(v+1, v+n+1);

    now = v[1];
    for(i=2; i<=n; ++i)
    {
        if(v[i].left < now.right + EPS) {
            now.left = max(v[i].left, now.left);
            now.right = min(now.right, v[i].right);
        }
        else{
            now = v[i];
            segments++; }
    }

    printf("%d", segments);

    return 0;
}