Cod sursa(job #919449)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 17:44:53
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
  
using namespace std;
  
struct interv
{
    double x,y;
};
  
struct cmp
{
    bool operator()(interv x,interv y)
    {
        return x.x<y.x;
    }
};
  
interv a[200001],b[200001];
  
int main()
{
    int i,x,y1,y2,aux,n,sol=2,n1=0,n2=0;
    double z;
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d %d",&x,&y1,&y2);
        if (y1>y2)
        {
            aux=y1;
            y1=y2;
            y2=aux;
        }
        if (x>0)
        {
            ++n1;
            a[n1].x=(double)y1/x;
            a[n1].y=(double)y2/x;
        }
        else
        {
            ++n2;
            b[n2].x=-(double)y1/x;
            b[n2].y=-(double)y2/x;
        }
    }
    sort(a+1,a+n1+1,cmp());
    z=a[1].y;
    for (i=2;i<=n1;++i)
        if (a[i].x>z||a[i].y<z)
        {
            if (a[i].x>z)
                ++sol;
            z=a[i].y;
        }
    sort(b+1,b+n2+1,cmp());
    z=b[1].y;
    for (i=2;i<=n2;++i)
        if (b[i].x>z||b[i].y<z)
        {
            if (b[i].x>z)
                ++sol;
            z=b[i].y;
        }
    printf("%d\n",sol);
    return 0;
}