Cod sursa(job #1147948)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 20 martie 2014 12:10:36
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream>
#include<algorithm>

using namespace std;
const int inf = 1000000000;
int n,x[10000],y[10000],b[20000000],k=0;
float a[20000000];

int factorial(int x){
	int p=1;
	for(int i=1;i<=x;i++)p=p*i;
	return p;
}

void algsort1(unsigned l,unsigned r){
	unsigned i=l,j=r;
	float  mij = a[(l+r)/2];
	do{
		while(a[i]<mij)i++;
		while(mij<a[j])j--;
		if (i<=j){
		    swap(a[i],a[j]);
		//	swap(b[i],b[j]);				
			i++;
			j--;
		}		
	}while(i<=j);
	if(l<j)algsort1(l,j);
    if(i<r)algsort1(i,r);
}

int main(){
	ifstream fin("trapez.in");
	ofstream fout("trapez.out");
	
	fin>>n;
	
	for(int i=1;i<=n;i++){
		fin>>x[i]>>y[i];		
	}
	
	for(int i=1;i<=n;i++)
	 for(int j=i+1;j<=n;j++){
	  k++;
	  if(x[i]==x[j])a[k]=inf;	  
	  else a[k] = (float)(y[i]-y[j])/(x[i]-x[j]);	
	 }
	
	algsort1(1,k);
	
	  int t,sol=0,i=1;
	 while(i<=k){
	 	t=1;
	 	while(a[i]==a[i+1]){
	 	i++;t++;	
	 	}
	 
       if(t>=2) sol +=factorial(t)/(2*factorial(t-2));
       i++;
	 }
	 
	fout<<sol;
	
}