Cod sursa(job #220008)

Utilizator Mishu91Andrei Misarca Mishu91 Data 9 noiembrie 2008 11:24:45
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct ray{float li, lf;};

vector <ray> V1, V2;
int Sol, N;

void citire()
{
    int x, y1, y2;
    ray r;
    scanf("%d",&N);

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

        float a = (float)y1 / x;
        float b = (float)y2 / x;
        if(a > b)
            r.li = b, r.lf = a;
        else
            r.li = a, r.lf = b;

        if(x > 0)
            V1.push_back(r);
        else
            V2.push_back(r);
    }

}

struct cmp
{
    bool operator() (const ray a, const ray b) const
    {
        return ((a.li < b.li) || (a.li == b.li && b.lf > a.lf));
    }
};

void solve(vector <ray> V)
{
    ray act = V.front();
    for(vector<ray>::iterator it = V.begin() + 1; it != V.end(); ++it)
    {
        if((it -> lf) > act.li)
            if(act.lf > it -> lf)
                act.lf = it -> lf;
        else
            ++Sol, act = *it;
    }
}

int main()
{
    freopen("rays.in","rt",stdin);
    freopen("rays.out","wt",stdout);
    citire();
    sort(V1.begin(), V1.end(), cmp());
    sort(V2.begin(), V2.end(), cmp());
    solve(V1);
    solve(V2);
    printf("%d\n",Sol);
}