Cod sursa(job #478464)

Utilizator nautilusCohal Alexandru nautilus Data 18 august 2010 19:51:35
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
#define dmax 1005
#define dmax2 1001000
using namespace std;

long long n,x[dmax],y[dmax],k,px[dmax2],py[dmax2],paralelox,paraleloy;
long long total;

void pante()
{
 long long i,j,auxx,auxy;
 
 for (i=1; i<n; i++)
	 for (j=i+1; j<=n; j++)
		 {
		  auxx=x[j]-x[i];
		  auxy=y[j]-y[i];
		  
		  if (auxx==0)
			  paraleloy++; else
			  if (auxy==0)
				  paralelox++; else
				  {
				   k++;
				   px[k]=auxx;
				   py[k]=auxy;
				  }
		 
		  if ((px[k]<0 && py[k]<0) || (py[k]<0))
			  {
			   px[k]=px[k]*(-1);
			   py[k]=py[k]*(-1);
			  }
		 }
}


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


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

long long comb(long long n)
{
 if (n==2)
	 return 1; else
	 return ((n-1)*n)/2;
}

void numarare()
{
 long long i,nr=1;
	
 if (paralelox > 1)
	 total+=comb(paralelox);
 
 if (paraleloy > 1)
	 total+=comb(paraleloy);
 
 for (i=2; i<=k; i++)
	 if (px[i-1]*py[i] == py[i-1]*px[i])
		 nr++; else
		 {
		  if (nr>1)
			  total+=comb(nr);
		  nr=1;
		 }
 if (nr>1)
	 total+=comb(nr);
}


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