Cod sursa(job #950644)

Utilizator vlad2309pascariu vlad vlad2309 Data 17 mai 2013 14:07:02
Problema Rays Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rays.in"); ofstream g("rays.out");
const int Nmax=200002;
struct segment {long long x,y1,y2;};
int n,nv,nu,nr,i,j;
long long X,Y;
segment v[Nmax],u[Nmax];
int main()
{   f>>n;
	while(n--) 
	{	segment seg;
		f>>seg.x>>seg.y1>>seg.y2;
		if(seg.y1>seg.y2) swap(seg.y1,seg.y2);
        if(seg.x>0) v[++nv]=seg; else {seg.x=-seg.x; u[++nu]=seg;}
    }
	if(nv)
	{for(i=1;i<nv;i++)
		for(j=i+1;j<=nv;j++)
			if(v[i].y2*v[j].x>v[j].y2*v[i].x) swap(v[i],v[j]);
		nr++; X=v[1].x,Y=v[1].y2;
		for(i=2;i<=nv;++i)
			if(X*v[i].y1>Y*v[i].x) {nr++; X=v[i].x; Y=v[i].y2;}
	}
	if(nu)
	{for(i=1;i<nu;i++)
		for(j=i+1;j<=nu;j++)
			if(u[i].y2*u[j].x>u[j].y2*u[i].x) swap(u[i],u[j]);		
		nr++; X=u[1].x,Y=u[1].y2;
		for(i=2;i<=nu;++i)
			if(X*u[i].y1>Y*u[i].x) {nr++; X=u[i].x; Y=u[i].y2;}
	}
	g<<nr<<'\n'; g.close(); return 0;
}
/*
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("rays.in"); ofstream g("rays.out");
struct segment {int x,y1,y2;};
int n,nr,X,Y;
vector <segment> v,u;
inline int cmp(const segment &a, const segment &b)
{   if(1LL*a.x*b.y2>1LL*b.x*a.y2) return 1; else return 0;}
int main()
{   f>>n;
    while(n--)
    {   segment seg;
        f>>seg.x>>seg.y1>>seg.y2;
        if(seg.y1>seg.y2) swap(seg.y1,seg.y2);
        if(seg.x>0) v.push_back(seg); else {seg.x=-seg.x; u.push_back(seg);}
    }
    sort(v.begin(),v.end(),cmp);
    if(v.size()!=0)
    {   ++nr; X=v[0].x,Y=v[0].y2;
        for(unsigned i=1; i<v.size(); ++i)
            if(1LL*X*v[i].y1>1LL*Y*v[i].x) {nr++; X=v[i].x; Y=v[i].y2;}
    }
    sort(u.begin(),u.end(),cmp);
    if(u.size()!=0)
    {   ++nr; X=u[0].x,Y=u[0].y2;
        for(unsigned i=1; i<u.size(); ++i)
            if(1LL*X*u[i].y1>1LL*Y*u[i].x) {nr++; X=u[i].x; Y=u[i].y2;}
    }
    g<<nr<<'\n'; g.close(); return 0;
}
*/