Cod sursa(job #935556)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 3 aprilie 2013 21:24:05
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define y first
#define x second
const double EPS=1.e-14;
using namespace std;
vector< pair<double , double> > v , b;
int n , x , y1 , y2;
double r;
int  nr;
int main()
{
    freopen("rays.in" , "r" , stdin);
    freopen("rays.out" , "w" , stdout);
    scanf("%d" , &n);
    for(int i=1 ; i<=n ; ++i)
    {
        scanf("%d %d %d" , &x , &y1 , &y2);
        if(y1 > y2)
            swap(y1 , y2);
        ///calculez tg de unghiuri
        if(x > 0)
            v.push_back(make_pair( (double) 1.0000*y2/x , (double) 1.0000*y1/x));
        else
            b.push_back(make_pair( (double) -1.0000*y2/x , (double) -1.0000*y1/x));
    }
    sort(v.begin() , v.end());
    sort(b.begin() , b.end());
    ///acum fac greedy pe unghiuri ca la reactivi
    /// pt v
    r=b[0].y;
    nr=1;
    for(int i=1 ; i<b.size() ; ++i)
        if(b[i].x - r > EPS)
            ++nr , r=b[i].y;
    r=v[0].y;
    nr++;
    for(int i=1 ; i<v.size() ; ++i)
        if(v[i].x - r > EPS)
            ++nr , r=v[i].y;
    printf("%d\n" , nr);
    return 0;
}