Cod sursa(job #1519557)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 7 noiembrie 2015 15:03:56
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
int n,n1,n2,i,viz[200001],NR,ultim1,ultim2;
double x,y1,y2;
struct date
{
    int ord;
    double sus,jos;
}v1[200001],v2[200001],v3[200001],v4[200001];

int cmp(date A,date B)
{
    if(A.sus==B.sus)
        return A.jos<B.jos;
    else
        return A.sus<B.sus;
}
int cmp2(date A,date B)
{
    if(A.jos==B.jos)
        return A.sus<B.sus;
    else
        return A.jos<B.jos;
}

int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y1>>y2;
        if(y1>y2)
            swap(y1,y2);
        if(x>0)
        {
            n1++;
            v1[n1].ord=i;
            v2[n1].ord=i;
            v1[n1].jos=y1/x;
            v1[n1].sus=y2/x;
            v2[n1].jos=v1[n1].jos;
            v2[n1].sus=v1[n1].sus;
        }
        else
        {
            n2++;
            x=-x;
            v3[n2].ord=i;
            v4[n2].ord=i;
            v3[n2].jos=y1/x;
            v3[n2].sus=y2/x;
            v4[n2].jos=v3[n2].jos;
            v4[n2].sus=v3[n2].sus;
        }
    }

    sort(v1+1,v1+n1+1,cmp);
    sort(v2+1,v2+n1+1,cmp2);
    sort(v3+1,v3+n2+1,cmp);
    sort(v4+1,v4+n2+1,cmp2);

    ultim1=1;
    NR=0;
    for(i=1;i<=n1;i++)
    {
        if( viz[v1[i].ord] == 0 )
        {
            viz[v1[i].ord] = 1;
            NR++;
            while( v2[ultim1].jos <= v1[i].sus && ultim1 <= n1)
            {
                viz[v2[ultim1].ord] = 1;
                ultim1++;
            }
        }
    }

    ultim2=1;
    for(i=1;i<=n2;i++)
    {
        if( viz[v3[i].ord] == 0 )
        {
            viz[v3[i].ord] = 1;
            NR++;
            while( v4[ultim2].jos <= v3[i].sus && ultim2 <= n2)
            {
                viz[v4[ultim2].ord] = 1;
                ultim2++;
            }
        }
    }
    fout<<NR;
    return 0;
}