Cod sursa(job #2244876)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 23 septembrie 2018 22:33:40
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <fstream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#define VAL 200005
#define CONST 57.295779

using namespace std;

struct eveniment
{
    long double nr;
    int inter;
    char semn;
};

eveniment EV[2*VAL], EV2[2*VAL];

int N, M1, M2, i, j, st[VAL], top;
int X[VAL], Y1[VAL], Y2[VAL], ANS;
long double A, B;
bool ok[VAL];

void Unghi(long double &U, long long X, long long Y)
{
    U=atan2(Y, X);
    U+=90;
    if (U>=360)
        U-=360;
}

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

char buff[VAL];
int poz=0;

int citeste()
{
    int semn=1, nr=0;
    while (buff[poz]<'0' || '9'<buff[poz])
    {
        if (buff[poz]=='-')
            semn=-1;
        if (++poz==VAL)
            fread(buff, 1, VAL, stdin), poz=0;
    }
    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        nr=nr*10+buff[poz]-'0';
        if (++poz==VAL)
            fread(buff, 1, VAL, stdin), poz=0;
    }
    return nr*semn;
}

int main()
{
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);
    N=citeste();
    for (i=1; i<=N; i++)
    {
        X[i]=citeste();
        Y1[i]=citeste();
        Y2[i]=citeste();
        Unghi(A, abs(X[i]), Y1[i]);
        Unghi(B, abs(X[i]), Y2[i]);
        if (A>B)
            swap(A, B);
        if (X[i]<0)
        {
            EV[++M1].nr=A;
            EV[M1].semn='+';
            EV[M1].inter=i;
            EV[++M1].nr=B;
            EV[M1].semn='-';
            EV[M1].inter=i;
        }
        else
        {
            EV2[++M2].nr=A;
            EV2[M2].semn='+';
            EV2[M2].inter=i;
            EV2[++M2].nr=B;
            EV2[M2].semn='-';
            EV2[M2].inter=i;
        }
    }
    sort(EV+1, EV+M1+1, cmp());
    sort(EV2+1, EV2+M2+1, cmp());
    for (i=1; i<=M1; 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--;
                }
            }
        }
    }
    top=0;
    for (i=1; i<=M2; i++)
    {
        if (EV2[i].semn=='+')
            st[++top]=EV2[i].inter;
        else
        {
            if (ok[EV2[i].inter]==false)
            {
                ANS++;
                while (top>0)
                {
                    ok[st[top]]=true;
                    top--;
                }
            }
        }
    }
    printf("%d\n", ANS);
    return 0;
}