Cod sursa(job #429547)

Utilizator nautilusCohal Alexandru nautilus Data 30 martie 2010 11:34:47
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<fstream>
#define dmax 1002
#define dmax2 1001000
using namespace std;

long n,nr,numar,ox,oy;
long x[dmax],y[dmax];
long pantasus[dmax2],pantajos[dmax2];

void generare()
{
 long i,j;	
 long pantasusaux,pantajosaux;

 for (i=1; i<=n-1; i++)
	 for (j=i+1; j<=n; j++)
		 {
		  pantasusaux=x[i]-x[j];
		  pantajosaux=y[i]-y[j];
		  
		  if (pantasusaux==0)
			  oy++; else
			  if (pantajosaux==0)
				  ox++; else
				  {
				   nr++;
				   pantasus[nr]=pantasusaux;
				   pantajos[nr]=pantajosaux;
				  }
		 }
}

long coef(long a, long b)
{
 if (a*b>=0)
	 return 1;
 return -1;
}

long divide(long st, long dr)
{
 long x=pantasus[st],y=pantajos[st];
 
 while (st<dr)
	 {
	  while (st<dr && y*pantasus[dr]>=x*pantajos[dr]*coef(y,pantajos[dr]))
		  dr--;
	  pantasus[st]=pantasus[dr];
	  pantajos[st]=pantajos[dr];
	  while (st<dr && y*pantasus[st]<=x*pantajos[st]*coef(y,pantajos[st]))
		  st++;
	  pantasus[dr]=pantasus[st];
	  pantajos[dr]=pantajos[st];
	 }		 
 pantasus[st]=x;
 pantajos[st]=y;
 
 return st;
}

void qsort(long p, long q)
{
 long m=divide(p,q);	
 
 if (m-1>p)
	 qsort(p,m-1);
 if (m+1<q)
	 qsort(m+1,q);
}

long comb (long n, long k)
{
 long i,nr1=1,nr2=1,nr3=1;
 
 for (i=2; i<=n; i++)
	 {
	  nr1=nr1*i;
	  if (i<=n-k)
		  nr2=nr2*i;
	  if (i<=k)
		  nr3=nr3*i;
	 }
 
 return nr1/(nr2=nr3);
}

void numarare()
{
 long i,pi,pf;
	
 pi=1; pf=1;
 for (i=2; i<=nr; i++)
	if (pantasus[i]*pantajos[i-1]==pantasus[i-1]*pantajos[i])
		pf++; else
		{
		 if (pf!=pi)
			numar=numar+comb(pf-pi+1,2);
		 pi=i; pf=i;
		}

 if (ox>1)
	 numar=numar+comb(ox,2);
 if (oy>1)
	 numar=numar+comb(oy,2);
}

int main()
{
 long i;
	
 ifstream fin("trapez.in");
 fin>>n;
 for (i=1; i<=n; i++)
	 fin>>x[i]>>y[i];
 
 generare();
 
 qsort(1,nr);
	
 numarare();
 
 ofstream fout("trapez.out");
 fout<<numar;
 
 fin.close();
 fout.close();
 
 return 0;
}