Cod sursa(job #917469)

Utilizator smaraldaSmaranda Dinu smaralda Data 17 martie 2013 22:21:05
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
#define eps 1.e-14
using namespace std;
struct SEGM { double x,y; };
SEGM st[200010],dr[200010];
bool comp (SEGM unu, SEGM doi)
{
    return unu.x-doi.x<=-eps;
}
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int i,N,s,d,res,x,y1,y2;
    double tg;
    scanf("%d",&N);
    s=d=0;
    for(i=1;i<=N;i++)
        {
            scanf("%d%d%d",&x,&y1,&y2);
            if(y1>y2) swap(y1,y2);
            if(x<0)
                {
                    x=-x;
                    st[++s].x=(double)y1/x;
                    st[s].y=(double)y2/x;
                }
            else
                {
                    dr[++s].x=(double)y1/x;
                    dr[s].y=(double)y2/x;
                }
        }
    res=2;
    sort(st+1,st+1+s,comp);
    sort(dr+1,dr+1+d,comp);
    tg=st[1].y;
    for(i=2;i<=s;i++)
        if(st[i].y>tg)
            {
                res++;
                tg=st[i].y;
            }
        else
            tg=st[i].y;

    tg=dr[1].y;
    for(i=2;i<=d;i++)
        if(st[i].y>tg)
            {
                res++;
                tg=st[i].y;
            }
        else
            tg=st[i].y;
    printf("%d\n",res);
    return 0;
}