Cod sursa(job #1900915)

Utilizator antanaAntonia Boca antana Data 3 martie 2017 17:30:02
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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;
    }
} a[MAXN], b[MAXN], now;

int n, nra, nrb;

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

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

    scanf("%d", &n);

    for(i=1; i<=n; ++i) {
        scanf("%d%d%d", &x, &y1, &y2);

        if(y1 > y2) swap(y1, y2);

        if(x > 0) {
            a[++nra].left = atan2(y1, x);
            a[nra].right = atan2(y2, x); }
        else
        {
            b[++nrb].left = atan2(y1, -x);
            b[nrb].right = atan2(y2, -x); } }


    sort(a+1, a+nra+1);
    sort(b+1, b+nrb+1);

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

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

    printf("%d", segments);

    return 0;
}