Cod sursa(job #1150653)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 23 martie 2014 13:51:16
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream>
#include<algorithm>

using namespace std;

int n,x[10000],y[10000],k=1;
long long p1[20000000],p2[20000000],doi=0,unu=0;



void algsort1(unsigned l,unsigned r){
	unsigned i=l,j=r;
	int  mij1 = p1[(l+r)/2],mij2=p2[(l+r)/2];
	do{
		while((float)mij1/mij2>(float)p1[i]/p2[i])i++;
		while((float)p1[j]/p2[j]>(float)mij1/mij2)j--;
		if (i<=j){
		    swap(p2[i],p2[j]);
			swap(p1[i],p1[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];		
	}
	
	int a,b;
	
	for(int i=1;i<=n;i++)
	 for(int j=i+1;j<=n;j++){
	  if (x[i]-x[j]==0) unu++;
          else if (y[i]-y[j]==0) doi++;
          else {
                 a=(y[i]-y[j]);
                 b=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
                 p1[k]=a*a;
                 if (x[i]<x[j]&&y[i]>y[j]) p1[k]*=-1;
                 else if (x[i]>x[j]&&y[i]<y[j]) p1[k]*=-1;
                 p2[k]=b;k++;
                 }	
	 }
	
	algsort1(1,k-1);
	
	  int t,i=1;
	  long long sol=0;
	 do{
	 	t=1;
	 	while(p1[i]*p2[i+1]==p2[i]*p1[i+1]){
	 	i++;t++;	
	 	}
	 
       if(t>=2) //sol +=factorial(t)/(2*factorial(t-2));
       sol+=(t*(t-1))/2;
       i++;
	 }while(i<k-1);
	 if(unu>1)
	 sol+=(unu*(unu-1))/2;
	 if(doi>1)
	 sol+=(doi*(doi-1))/2;
	 
	fout<<sol;
	
}