Cod sursa(job #606578)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 4 august 2011 20:54:35
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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;
}