Cod sursa(job #220029)

Utilizator Mishu91Andrei Misarca Mishu91 Data 9 noiembrie 2008 12:03:14
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 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);
    }

}

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

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();
    ++Sol;
    for(vector<ray>::iterator it = V.begin() + 1; it != V.end(); ++it)
    {
        if((act.lf) >= it -> li)
        {
            act.li = it -> li;
            act.lf = min(act.lf, it -> lf);
        }

        else
            ++Sol, act = *it;
    }
}

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