Cod sursa(job #113621)

Utilizator astronomyAirinei Adrian astronomy Data 10 decembrie 2007 21:51:09
Problema Rays Scor Ascuns
Compilator cpp Status done
Runda Marime 1.45 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

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

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

int cmp(double a, 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 = ((double)Y1[i] / X[i]) * XINF, S[h].y = +1;
            ++h, S[h].x = ((double)Y2[i] / X[i]) * XINF, S[h].y = -1;
        }

    sort(S+1, S+h+1, cmp_pair);

    for (i = 1, ql = 0; i <= h+1; i++)
        if (S[i].y == +1)
            ql++;
        else
            cnt += (ql != 0), ql = 0;

    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;
    
}