Cod sursa(job #1027414)

Utilizator stanescu.raduRadu Stanescu stanescu.radu Data 12 noiembrie 2013 19:35:16
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>

using namespace std;

ifstream f ("trapez.in");
ofstream out("trapez.out");

int n,i,x[1005],y[1005],j,nr,k,s;
double p[1000005];

void merge (int st, int m, int dr)
{
	int i=st, j=m+1;
	double aux[100005];
	int k=0;
	while (i<=m && j<=dr)
	{
		if (p[i]<=p[j])
		{
			aux[++k]=p[i];
			i++;
		}
		else 
		{
			aux[++k]=p[j];
			j++;
		}
	}
	while (i<=m) aux[++k]=p[i++];
	while (j<=dr) aux[++k]=p[j++];
	k=0;
	for (i=st;i<=dr;i++) p[i]=aux[++k];
}

void mergesort(int st, int dr)
{
	int m;
	if ((dr-st)<1) return;
	else 
	{
		m=(st+dr)/2;
		mergesort(st,m);
		mergesort(m+1,dr);
		merge(st,m,dr);
	}
}

int main  ()
{
	f>>n;
	for (i=1;i<=n;i++)
		f>>x[i]>>y[i];
	k=0;
	for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++)
		{
			if (x[i]==x[j]) p[++k]=99999999;
			else p[++k]=((y[j]-y[i])*1.0)/(x[j]-x[i]);
		}
	mergesort(1,k);
	s=0;
	nr=1;
	for (i=2;i<=k;i++)
	{
		if (p[i]==p[i-1]) nr++;
		else 
		{
			s+=nr*(nr-1)/2;
			nr=1;
		}
	}
	s+=nr*(nr-1)/2;
	out<<s;
	f.close();
	out.close();
	return 0;
}