Cod sursa(job #484295)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 13 septembrie 2010 14:54:13
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<stdio.h>
#include <math.h>
#include <algorithm>
#define Nmax 1502
#define eps 0.001
#define D double
#define INF 100000000.0

using namespace std;

struct punct{ D x,y; } P[Nmax],PM,PV;
D A,B,C,AP,lat,hx,hy;
int N,triang;

inline D Abs( D a){ return a>0?a:-a; }
inline int egal( D a, D b){
	return Abs(a-b)<eps;
}
inline int cmp(punct a, punct b){
	return ( a.x<b.x || ( egal(a.x,b.x) && (a.y<b.y || egal(a.y,b.y)) ) );
}

inline int search(int l,int r,punct PV){
	int i,step;
	for( step=1; l+step<=N; step<<=1 );
	for(i=l; step; step>>=1)
		if(i+step<=N && cmp(P[i+step],PV))
			i+=step;
	if( egal(P[i].x,PV.x) && egal(P[i].y,PV.y) ) return 1;
	return 0;
}	

int main(){
	int i,j;
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	scanf("%d",&N);
	for(i=1;i<=N;++i) scanf("%lf%lf",&P[i].x,&P[i].y);
	
	sort(P+1,P+N+1,cmp);
	
	for(i=1;i<=N-1;++i)
		for(j=i+1;j<=N;++j){
			PM.x=(P[i].x+P[j].x);
			PM.y=(P[i].y+P[j].y);
			lat=(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y);
			
			if( P[j].x != P[i].x )
				A=(P[j].y-P[i].y)/(P[j].x-P[i].x);
			else A=INF;
			B=-1;
			C=P[i].y-A*P[i].x;
			
			if( A!=0 ) AP=-1/A;
			else AP=INF;
		
			hx=(sqrt(3))*Abs(P[i].y-P[j].y);
			if(hx!=0)hy=hx*AP;
			else hy=sqrt(lat*0.75)*2; // ar veni si -hx^2 da e 0
			
			// cele 2 solutii pentru ecuatie
			PV.x=(PM.x+hx)/2; // am imp la sf prin 2 ca sa evitimp repetate
			PV.y=(PM.y+hy)/2;
			triang += search(1,N,PV);
			
			PV.x=(PM.x-hx)/2;
			PV.y=(PM.y-hy)/2;
			triang += search(1,N,PV);
		}
	
	printf("%d\n",triang/3);
	fclose(stdin); fclose(stdout);
	return 0;
}