Cod sursa(job #753887)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 30 mai 2012 18:28:55
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;

ofstream out("rays.out");

struct dreapta {int x,y1,y2;};

int n,lst,ldr,sol;
pair<double,double> st[200100],dr[200100];
dreapta a[200100];

struct cmp
{
	bool operator()(const pair<double,double> &a,const pair<double,double> &b)const
	{
		if(a.first==b.first)
		{
			return a.second<b.second;
		}
		return a.first<b.first;
	}
};

inline int make(pair<double,double> a[],int lung)
{
	int ret=0;
	sort(a+1,a+lung+1,cmp());

	for(int i=1;i<=lung;++i)
	{
		//cout<<a[i].first<<' '<<a[i].second<<'\n';
	}
	cout<<'\n';
	
	pair<double,double> var;
	var=a[1];
	a[lung+1]=make_pair(2000000000,2000000000);
	
	for(int i=2;i<=lung+1;++i)
	{
		//cout<<var.first<<" "<<var.second<<"   "<<a[i].first<<" "<<a[i].second<<"\n";
		//cout<<max(var.first,a[i].first)<<" "<<min(var.second,a[i].second)<<"\n";
		
		if(max(var.first,a[i].first)<=min(var.second,a[i].second))
		{
			var.first=max(var.first,a[i].first);
			var.second=min(var.second,a[i].second);
		}
		else
		{
			//cout<<var.first<<" "<<var.second<<"   "<<a[i].first<<" "<<a[i].second<<"\n";
			//exit(0);
			var=a[i];
			++ret;
		}
	}
	
	return ret;
}

int main()
{
	ifstream in("rays.in");
	
	in>>n;
	for(int i=1;i<=n;++i)
	{
		in>>a[i].x>>a[i].y1>>a[i].y2;
		if(a[i].x<0)
		{
			++lst;
			st[lst].first=1.0*a[i].y1/a[i].x;
			st[lst].second=1.0*a[i].y2/a[i].x;
			if(st[lst].first>st[lst].second) swap(st[lst].first,st[lst].second);
		}
		else
		{
			++ldr;
			dr[ldr].first=1.0*a[i].y1/a[i].x;
			dr[ldr].second=1.0*a[i].y2/a[i].x;
			if(dr[ldr].first>dr[ldr].second) swap(dr[ldr].first,dr[ldr].second);
		}
	}
	
	sol=make(st,lst)+make(dr,ldr);
	
	out<<sol<<'\n';
	out.close();
	return 0;
}