Cod sursa(job #1153982)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 25 martie 2014 21:33:20
Problema Rays Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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
        {
            d.x *= -1;
            dn[++l] = d;
        }

    }
}

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