Cod sursa(job #407285)

Utilizator otilia_sOtilia Stretcu otilia_s Data 2 martie 2010 10:49:34
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
using namespace std;
const int NMAX=1002;
const int pMAX=1000002;
int X[NMAX],Y[NMAX],n;
int pX[pMAX],pY[pMAX];

void citire()
{
	ifstream fin("trapez.in");
	fin>>n; int i;
	for (i=1;i<=n;++i) fin>>X[i]>>Y[i];
	fin.close();
}
/*
void qsort(int st, int dr)
{ int i=st,j=dr,mij=(st+dr)/2;
  do
  {
	while ((pY[i]*pX[mij]<pY[mij]*pX[i])&&(i<n)) ++i;
	while ((pY[mij]*pX[j]<pY[j]*pX[mij])&&(j>1)) --j;
	if (i<=j)
		{
		 int aux=pX[i];pX[i]=pX[j]; pX[j]=aux;
			 aux=pY[i];pY[i]=pY[j]; pY[j]=aux;
		 ++i; --j;
		}
  }
  while (i<=j);
  if (i<dr) qsort(i,dr);
  if (st<j) qsort(st,j);
}
*/

int pivot(int st, int dr)
{ short di=1, dj=0;
	while (st<dr)
	{ 	
		if ((pX[dr]==0 &&pX[st]!=0) || (pX[st]!=0 && pY[st]*pX[dr]>pY[dr]*pX[st]))
			{ int aux=pX[st]; pX[st]=pX[dr]; pX[dr]=aux;
				  aux=pY[st]; pY[st]=pY[dr]; pY[dr]=aux;
				  di^=1; dj^=1;
			}
		st+=di; dr-=dj;
	}
	return st;
}

void qsort(int st, int dr)
{
	if (st<dr) { int p=pivot(st,dr);
				 qsort(st,p-1);
				 qsort(p+1,dr);
			   }
}

int main()
{
	citire();
	int np=0,i,j;
	for (i=1;i<n;++i)
	 for (j=i+1;j<=n;++j)
	 { int x,y;
		x=X[i]-X[j]; y=Y[i]-Y[j];
		if (x<0) { y*=-1; x*=-1;}
		pX[++np]=x; pY[np]=y;
	 }
	qsort(1,np);
	long long S=0;
	for (i=1;i<=np;++i)
	{
		int i1=i;
		for (;(i<np)&&(pY[i]*pX[i+1]==pY[i+1]*pX[i]);++i);
		int nr=i-i1+1;
		S+=(nr*(nr-1)/2);
	}
	ofstream fout("trapez.out");
	fout<<S;
	fout.close();
	return 0;
}