Cod sursa(job #1153916)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 25 martie 2014 20:39:37
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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, l;

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+1,dp+k+1,cmp);
    sort(dn+1,dn+l+1,cmp);

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

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

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

    scanf("%d", &n);
    for (int i = 1; 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[1].x;
        y = v[1].y1;
        for (int i=2; i<=lg; ++i)
        {
            if ( v[i].x*y < v[i].y1*x )
            {
                ++rez;
                x = v[i].x;
                y = v[i].y2;
            }
        }
    }
}