Cod sursa(job #1153897)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 25 martie 2014 20:20:38
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define NMAX 200005
using namespace std;

struct dreapta
{
    long long x, y1, y2;
};


dreapta dp[NMAX]; //pozitive
dreapta dn[NMAX]; //negative

int n, nr, rez;
int k = -1, l = -1;

void citire();
void solve(dreapta v[], int lg);

bool cmp(dreapta a, dreapta b)
{
    return a.x*b.y2 < a.y2*b.x;
}
int main()
{
    freopen("rays.in", "r",stdin);
    freopen("rays.out", "w",stdout);

    citire();

    sort(dp,dp+k,cmp);
    sort(dn,dn+l,cmp);

    solve(dp,k+1);
    solve(dn,l+1);

    printf("%d\n",rez);
    return 0;
}

void citire()
{
    //int x, y1, y2;
    dreapta d;

    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld %lld %lld",&d.x, &d.y1, &d.y2);
        if (d.y1 > d.y2) swap(d.y1, d.y2);

        if (d.x>0)
            dp[++k] = d;
        else
            dn[++l] = d;
    }
}

void solve(dreapta v[], int lg)
{
    long long x, y;
    if (lg>0)
    {
        x = v[0].x;
        y = v[0].y1;
        for (int i=0; i<lg; ++i)
        {
            if ( v[i].x*y <= v[i].y1*x )
            {
                ++rez;
                x = v[i].x;
                y = v[i].y2;
            }
        }
    }
}