Cod sursa(job #2244827)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 23 septembrie 2018 19:50:14
Problema Rays Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <cstdio>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
#define VAL 200005
#define PI 3.14159265

using namespace std;

int N, M, i, j, A, B, K, st[VAL], top;
int X[VAL], Y1[VAL], Y2[VAL], ANS;
double P[2*VAL], Angle;
bool ok[VAL];
map < double, int > H;

struct eveniment
{
    int nr, inter;
    char semn;
};

eveniment EV[2*VAL];

void Unghi(double &U, int X, int Y)
{
    U=atan2(Y, X)*180 / PI;
    U+=90;
    if (U>=360)
        U-=360;
}

bool cmp(eveniment A, eveniment B)
{
    if (A.nr!=B.nr)
        return A.nr<B.nr;
    if (A.semn=='+')
        return true;
    return false;
}

int main()
{
    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]);
        M++;
        Unghi(P[M], X[i], Y1[i]);
        M++;
        Unghi(P[M], X[i], Y2[i]);
    }
    sort(P+1, P+M+1);
    for (i=1; i<=M; i++)
    {
        if (P[i]!=P[i-1])
        {
            K++;
            H[P[i]]=K;
        }
    }
    M=0;
    for (i=1; i<=N; i++)
    {
        Unghi(Angle, X[i], Y1[i]);
        A=H[Angle];
        Unghi(Angle, X[i], Y2[i]);
        B=H[Angle];
        if (A>B)
            swap(A, B);
        EV[++M].nr=A;
        EV[M].semn='+';
        EV[M].inter=i;
        EV[++M].nr=B;
        EV[M].semn='-';
        EV[M].inter=i;
    }
    sort(EV+1, EV+M+1, cmp);
    for (i=1; i<=M; i++)
    {
        if (EV[i].semn=='+')
            st[++top]=EV[i].inter;
        else
        {
            if (ok[EV[i].inter]==false)
            {
                ANS++;
                while (top>0)
                {
                    ok[st[top]]=true;
                    top--;
                }
            }
        }
    }
    printf("%d\n", ANS);
    return 0;
}