Cod sursa(job #676997)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 9 februarie 2012 19:37:18
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
/*
    Fiecare dreapta verticala devine interval de tragere
intre 2 unghiuri. => numar minim de valori (pentru unghiuri)
pentru a atinge intervale (problema reactivi de pe infoarena)
    pot retine tangenta unghiurilor pentru a evita functiile
trigonometrice (atunci gestionez unghiurile din stanga
si dreapta separat (tragerile sunt semidrepte nu drepte))
    alta solutie decat cea oficiala (este suficienta
repartizarea unei drepte la o tragere (nu e nevoie sa se
considere multe trageri))
*/

#include <cstdio>
#include <algorithm>
using namespace std;

struct interval
{
    double a,b;
};

const int N_MAX = 200010;

int n,n1,n2;
interval v1[N_MAX], v2[N_MAX];

inline double min(double a, double b)
{
    return (a<b)?a:b;
}

interval indreptat(interval x)
{
    if (x.a <= x.b)
        return x;
    return (interval){x.b,x.a};
}

void citeste()
{
    int x,y1,y2;
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d",&x,&y1,&y2);
        if (x < 0)
            v1[++n1] = indreptat(interval{(double)y1/x,(double)y2/x});
        else
            v2[++n2] = indreptat(interval{(double)y1/x,(double)y2/x});
    }
}

bool inceput_crescator(interval x, interval y)
{
    return x.a < y.a;
}

int numara_trageri(interval v[], int n)
{
    int nrt = 1;
    int b_min = v[1].b;
    sort(v+1,v+n+1, inceput_crescator);
    for (int i = 2; i <= n; ++i)
        if (v[i].a <= b_min)
            b_min = min(b_min,v[i].b);
        else
        {
            ++nrt;
            b_min = v[i].b;
        }
    return nrt;
}

int main()
{
    int nrt = 0;
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    citeste();
    nrt += numara_trageri(v1,n1);
    nrt += numara_trageri(v2,n2);
    printf("%d",nrt);
    return 0;
}