Cod sursa(job #644285)

Utilizator elfusFlorin Chirica elfus Data 5 decembrie 2011 23:14:16
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define EPS 0.000000001
#define PI 3.1415926535
#define LMAX 200100

using namespace std;

struct point
{
    int x, y, line;
} x[2 * LMAX];
bool events[LMAX], used[LMAX];
int st[2 * LMAX];

double unghi (point A) //unghiul OA in radiani
{
    double panta = (double)A.y / A.x, alfa = atan (panta);

    if (A.x > 0 && A.y > 0)
        return alfa;
    if (A.x < 0 && A.y >= 0)
        return PI - alfa;
    if (A.x < 0 && A.y < 0)
        return PI + alfa;
    return 2 * PI - alfa;
}

inline bool comp (point A, point B)
{
    return unghi (A) - unghi (B) <= EPS * (-1);
}

int main ()
{
    int i, N, x0, y1, y2, lenth = 0, sol = 0;

    freopen ("rays.in", "r", stdin);
    freopen ("rays.out", "w", stdout);

    scanf ("%d", &N);
    for (i = 1; i <= N; i ++)
    {
        scanf ("%d%d%d", &x0, &y1, &y2);
        x[++ lenth].x = x0; x[lenth].y = y1; x[lenth].line = i;
        x[++ lenth].x = x0; x[lenth].y = y2; x[lenth].line = i;
    }

    sort (x + 1, x + 2 * N + 1, comp); //Sortez punctele in functie de unghiul facut cu OX
    lenth = 0;
    for (i = 1; i <= N + N; i ++)
        if (!used[x[i].line])
            if (!events[x[i].line])
                st[++ lenth] = x[i].line, events[x[i].line] = true;
            else
            {
                sol ++;
                while (st[lenth] != x[i].line)
                    used[st[lenth --]] = 1;
                used[st[lenth --]] = 1;
            }
    printf ("%d", sol);
    return 0;
}