Cod sursa(job #932974)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 29 martie 2013 14:23:56
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 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 = 2;
    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;
}