Cod sursa(job #443360)

Utilizator bog29Antohi Bogdan bog29 Data 16 aprilie 2010 20:14:38
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<fstream>
#include<list>
#include<vector>
#include<algorithm>
#define dmax 1004
#define er 0.0000001
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");

long long n,sol;
double u;

vector<double>m;
vector<double>::iterator it,ir,iw;

struct point
{	long long x;
	long long y;
}	p[dmax];

typedef int (*compfn)(const void *,const void *);

int sf(struct point *a,struct point *b)
{	if(a->x != b->x)
		return a->x - b->x;
	return a->y - b->y;
}	

double mx(double k)
{	if(k<0)return -1 * k;
	return k;
}

int main()
{	int i,j;
	in>>n;
	for(i=0;i<n;i++)
		in>>p[i].x>>p[i].y;
	in.close();	
	qsort( (void*)&p, n, sizeof(struct point), (compfn)sf );
	for(i=1;i<n;i++)
		for(j=0;j<i;j++)
		{	u=( (double)p[i].y - (double)p[j].y) / (double)(p[i].x - (double)p[j].x);
			if( (double)(p[i].x - (double)p[j].x) == 0)
				u=1000;
			//out<<u<<" "<<j<<" "<<i<<"*\n";
			/*for(it=m.begin();it<m.end();it++)
				out<<*it<<" ";
			out<<"\n\n";*/
			if(i==1 && j==0)
				m.push_back(u);
			else if(u < m.front() )
			{	if( mx(u-m.front()) <= er)
				{	sol++; 
					//out<<u<<"***"<<m.front()<<'\n';
					//out<<mx((double)(u-m.front()) )<<"******\n";
				}	
				m.insert(m.begin() , 1, u);
			}
			else if(u > m.back() )
			{	
				if( mx(u-m.back() ) <= er)
				{	sol++; 
					//out<<u<<"***"<<m.back()<<'\n';
					//out<<mx( (double)(u-m.back()))<<"****\n";
				}
				m.push_back(u);		
			}	
			else	
			{	it=lower_bound(m.begin() , m.end() , u);
				ir=upper_bound(m.begin() , m.end() , u);
				/*if( mx(*it-u ) <= er)
				{	sol++; 
					out<<u<<"***"<<*it<<'\n';
					//out<<mx((double)(*it-u))<<"*******\n";
				}*/	
				ir=it+1;
				iw=it;
				while(mx(*iw-u ) <= er && iw > m.begin() )
				{	sol++;
					//out<<*iw<<"***"<<u<<'\n';
					iw=iw-1;
				}
				while(mx(*ir-u ) <= er && iw < m.end() )
				{	sol++;
					//out<<*ir<<"***"<<u<<'\n';
					ir=ir+1;
				}	
				if(it == m.begin() && mx(*it-u ) <= er )
					sol++;
				if(it == m.end() && mx(*it-u ) <= er )
					sol++;
				/*if( mx(*ir-u ) <=er)
				{	//sol++; 
					//out<<u<<"****"<<*ir<<'\n';
					//out<<mx((double)(*ir-u))<<"*********\n";
				}	*/
				m.insert( it , 1 , u);
			}	
		}	
	out<<sol;
	out.close();	
	return 0;
}