Cod sursa(job #932893)

Utilizator xxxcnmvxxxnume cpmplet xxxcnmvxxx Data 29 martie 2013 13:01:02
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in ("rays.in");
ofstream out ("rays.out");

struct interval
{
    double st, dr;
} St[200010], Dr[200010];

struct comp
{
    inline bool operator () (const interval &A, const interval &B){
        return A.st < B.st;
    }
};

int main()
{
    int N, N1 = 0, N2 = 0, i, x, y1, y2, Ans = -1;
    double last;

    in >> N;

    for (i = 1; i <= N; i ++){
        in >> x >> y1 >> y2;

        if (y2 < y1)
            y1 ^= y2 ^= y1 ^= y2;

        if (x < 0){
            ++ N1;
            St[N1].st = (double) y1 / x;
            St[N1].dr = (double) y2 / x;
        }
        else{
            ++ N2;
            Dr[N2].st = -(double) y1 / x;
            Dr[N2].dr = -(double) y2 / x;
        }
    }

    sort (St + 1, St + N1 + 1, comp ());
    sort (Dr + 1, Dr + N2 + 1, comp ());

    last = St[1].dr;
    for (i = 2; i <= N1; i ++)
        if (St[i].st > last || St[i].dr < last){
            if (St[i].st > last)
                ++ Ans;

            last = St[i].dr;
        }

    last = Dr[1].dr;
    for (i = 2; i <= N2; i ++)
        if (Dr[i].st > last || Dr[i].dr < last){
            if (Dr[i].st > last)
                ++ Ans;

            last = Dr[i].dr;
        }

    out << Ans;

    return 0;
}