Cod sursa(job #115682)

Utilizator filipbFilip Cristian Buruiana filipb Data 16 decembrie 2007 20:09:44
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define PII pair<long double, int>
#define NMax 200005
#define EPS 1e-12
#define ll long long
#define x first
#define y second

int N, X[NMax], Y1[NMax], Y2[NMax], q[NMax], uz[NMax], bst;
PII S[NMax<<1];

int cmp(long double a, long double b)
{
    if (fabs(a-b) < EPS) return 0;
    if (a > b) return +1;
    return -1;
}

int cmp_pair(const PII& a, const PII& b)
{
    int ok = cmp(a.x, b.x);

    if (ok)
        return ok == -1;
    return a.y > b.y;
}

int solve(int sg)
{
    int i, h = 0, cnt = 0, ql = 0;

    for (i = 1; i <= N; i++)
        if (X[i] * sg > 0)
        {
            X[i] *= sg;
            ++h, S[h].x = (long double)Y1[i] / X[i], S[h].y = +i;
            ++h, S[h].x = (long double)Y2[i] / X[i], S[h].y = -i;
        }

    if (!h)
        return 0;
        
    sort(S+1, S+h+1, cmp_pair);
    memset(uz, 0, sizeof(uz));

    for (i = 1, ql = 0; i <= h; i++)
    {
        if (S[i].y > 0)
            q[++ql] = S[i].y;            
        else if (!uz[-S[i].y])
        {        
            cnt ++;
            for (; ql > 0; ql--)
                uz[q[ql]] = 1;                
        }
        
    }

    return cnt;
}

int main(void)
{
    int i, aux;
    
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d %d", &X[i], &Y1[i], &Y2[i]);
        if (Y1[i] > Y2[i])
            aux = Y1[i], Y1[i] = Y2[i], Y2[i] = aux;
    }

    bst = solve(1) + solve(-1);
    printf("%d\n", bst);

    return 0;
    
}