Cod sursa(job #429478)

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

int n,nr,numar;
int x[dmax],y[dmax];
int pantasus[dmax2],pantajos[dmax2];

void generare()
{
 int i,j;	

 for (i=1; i<=n-1; i++)
	 for (j=i+1; j<=n; j++)
		 {
		  nr++;
		  pantasus[nr]=x[i]-x[j];
		  pantajos[nr]=y[i]-y[j];
		 }
}

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

int divide(int st, int dr)
{
 int 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(int p, int q)
{
 int m=divide(p,q);	
 
 if (m-1>p)
	 qsort(p,m-1);
 if (m+1<q)
	 qsort(m+1,q);
}

int comb (int n, int k)
{
 int 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()
{
 int 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;
		}
}

int main()
{
 int 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;
}