Cod sursa(job #1011599)

Utilizator lucky1992Ion Ion lucky1992 Data 16 octombrie 2013 23:43:16
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

#define x first
#define y second
#define K 1.0*sqrt(3)

typedef pair<double,double> Punct;
vector<Punct> Points;
int N, sol = 0;
Punct v1, v2;

bool cmp( Punct a, Punct b ){

	return (a.x < b.x) || ( ( fabs(a.x-b.x) < 0.001 ) && a.y < b.y );	
}

bool egal( Punct a, Punct b ){

	return fabs( a.x - b.x ) && fabs( a.y - b.y ) ;

}

Punct Varf( Punct a, Punct b ){

	Punct p;
	
	p.x = 0.5*( a.x + b.x ) - K/2*( b.y - a.y );
	p.y = 0.5*( a.y + b.y ) + K/2*( b.x - a.x );
	
	return p;
	
}

int cauta( int left, int right, Punct v ){
	
	int mid, sol = 0;
	
	while ( left <= right ){
	
		mid = (left+right)/2;

		if( fabs( Points[mid].x - v.x ) < 0.001 && fabs( Points[mid].y - v.y ) < 0.001 ){
			sol = 1;
			break;
		}
		else if( fabs( Points[mid].x - v.x ) < 0.001 ){
		
				if( Points[mid].y < v.y )
					left = mid + 1;
				else
					right = mid - 1;
		}
		else{
		
				if( Points[mid].x < v. x )
					left = mid + 1;
				else
					right = mid - 1;
		}
	}
	
		return sol;
		
}
			
			
		
int main(){

	freopen("triang.in", "r", stdin );
	freopen("triang.out", "w", stdout );
	scanf("%d", &N );
	
	Points.resize(N);
	
	for( int i = 0; i < N; i++ )
		scanf("%lf%lf", &Points[i].x, &Points[i].y );
	
	sort( Points.begin(), Points.begin()+N, cmp );

	
	for( int i = 0; i < N; i++ )
		for( int j = i+1; j < N; j++ ){
			v1 = Varf( Points[i], Points[j] );
			v2 = Varf( Points[j], Points[i] );
			sol += cauta( 0, N-1, v1 );
			sol += cauta( 0, N-1, v2 );
		}

	printf("%d\n", sol/3 );
	return 0;
	
}