Cod sursa(job #524125)

Utilizator klamathixMihai Calancea klamathix Data 20 ianuarie 2011 09:51:24
Problema Triang Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const double eps = 0.000001;
const int maxn = 1600;
const int P = 100000000;
const int mod = 104729;
const double pi = acos((double)-1);
ifstream fin("triang.in");
ofstream fout("triang.out");

int i , j , k , l , n;

struct point {
	double x;
	double y;
} p[maxn];

vector < point > H[mod];

bool cmp ( point A , point B ) {
	if ( A.x != B.x ) return A.x < B.x;
	return A.y < B.y;
}

double dabs ( double x ){
	if ( x < 0 ) return  -x;
return x;
}

int find (point A)
{
	int lf , rt , mid;
	for( lf = 1 , rt = n ; lf <= rt ; ) {
		mid = (lf + rt) >> 1;
		if ( dabs( p[mid].x - A.x ) < eps ) {
				if ( dabs(p[mid].y - A.y) < eps )
					return 1;
				else if ( p[mid].y < A.y )
					lf = mid + 1;
				else if ( p[mid].y > A.y )
					rt = mid - 1;
			}
		else if ( p[mid].x < A.x )
			lf = mid + 1;
		else if ( p[mid].x > A.x )
			rt = mid - 1;
	}
	return 0;
}

int counts ( point A , point B ) {
	
	point P1 , P2;
	double w = pi / 3;
	
	P1.x = (B.x + (A.x - B.x) * cos(w) - (A.y - B.y) * sin(w));
	P1.y = (B.y + (A.x - B.x) * sin(w) + (A.y - B.y) * cos(w));
	
	w *= -1;
	
	P2.x = (B.x + (A.x - B.x) * cos(w) - (A.y - B.y) * sin(w));
	P2.y = (B.y + (A.x - B.x) * sin(w) + (A.y - B.y) * cos(w));
	
	int cnt = find(P1);
	return cnt + find(P2);
}
	
int Solve()
{
	int i , j;
	int ans = 0;
	for( i = 1 ; i <= n ; ++i )
		for( j = i + 1 ; j <= n ; ++j )  
			ans += counts ( p[i] , p[j] );
		
	return ans / 3;
}

int main()
{
	fin >> n;
	for( i = 1 ; i <= n ; ++i ) {
		fin >> p[i].x >> p[i].y;
	}
	sort ( p + 1 , p + n + 1 , cmp);
	fout << Solve();
	
return 0;
}