Cod sursa(job #2076215)

Utilizator zhm248Mustatea Radu zhm248 Data 26 noiembrie 2017 12:37:50
Problema Rays Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct punct
{
    int x,y,nr;
    bool stare;
};

const double eps=1.e-14;
bool cmp1(punct a,punct b)
{
    if(fabs(((double)a.y/(double)a.x)-((double)b.y/(double)b.x))<eps)
        return a.stare>b.stare;
    else
        return ((double)a.y/(double)a.x)-((double)b.y/(double)b.x)<=-eps;
}

bool cmp2(punct a,punct b)
{
    if(fabs(((double)a.y/(double)a.x)-((double)b.y/(double)b.x))<eps)
        return a.stare>b.stare;
    else
        return ((double)a.y/(double)a.x)-((double)b.y/(double)b.x)>=eps;
}

punct v1[400001],v2[400001];
int t1[200001],t2[200001];
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int n,i,x,y1,y2,nr1=0,nr2=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d%d",&x,&y1,&y2);
        if(x>0)
        {
            nr1++;
            v1[(2*nr1)-1].x=v1[2*nr1].x=x;
            v1[(2*nr1)-1].y=y1;
            v1[2*nr1].y=y2;
            v1[(2*nr1)-1].nr=v1[2*nr1].nr=i;
            if(y1<=y2)
                v1[(2*nr1)-1].stare=1;
            else
                v1[2*nr1].stare=1;
        }
        else
        {
            nr2++;
            v2[(2*nr2)-1].x=v2[2*nr2].x=x;
            v2[(2*nr2)-1].y=y1;
            v2[2*nr2].y=y2;
            v2[(2*nr2)-1].nr=v2[2*nr2].nr=i;
            if(y1<=y2)
                v2[(2*nr2)-1].stare=1;
            else
                v2[2*nr2].stare=1;
        }
    }
    sort(v1+1,v1+(2*nr1)+1,cmp1);
    sort(v2+1,v2+(2*nr2)+1,cmp2);
    int sol=0;
    for(i=1;i<=2*nr1;++i)
    {
        if(v1[i].stare)
            t1[v1[i].nr]=i;
    }
    for(i=1;i<=2*nr2;++i)
    {
        if(v2[i].stare)
            t2[v2[i].nr]=i;
    }
    int poz=0;
    for(i=1;i<=2*nr1;++i)
    {
        if(v1[i].stare)
        {
            if(!v1[poz].stare)
                poz=i;
        }
        else
        {
            if(t1[v1[i].nr]>=poz)
            {
                sol++;
                poz=i;
            }
        }
    }
    poz=1;
    for(i=1;i<=2*nr2;++i)
    {
        if(v2[i].stare)
        {
            if(!v2[poz].stare)
                poz=i;
        }
        else
        {
            if(t2[v2[i].nr]>=poz)
            {
                sol++;
                poz=i;
            }
        }
    }
    printf("%d\n",sol);
    return 0;
}