Cod sursa(job #819880)

Utilizator deneoAdrian Craciun deneo Data 19 noiembrie 2012 20:02:44
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;

ifstream fin("triang.in");
ofstream fout("triang.out");

#define MAXN 1600

const double PI = 3.1415926;
const double EP = 0.00001;

pair<double, double> P[MAXN];
int N;

bool cmp (pair<double, double> a, pair<double, double> b) {
	return (b.first - a.first > EP) || ((fabs(b.first - a.first) < EP) && (b.second - a.second > EP)); 
}

bool cautare (double x, double y) {
	int st = 1, fn = N, m;
	
	while (st < fn) {
		m = (st + fn) / 2;
		if ((fabs(P[m].first - x) < EP) && (fabs(P[m].second - y) < EP))
			return 1;
		if (P[m].first - x > EP || ((fabs(P[m].first - x) < EP) && P[m].second - y > EP))
			fn = m - 1;
		else 
			st = m + 1;
	}
	
	return (P[st].first - x < EP) && (P[st].second - y < EP);
}

int main () {
	int i, j, rez = 0;
	
	fin >> N;
	for (i = 1; i <= N; ++i) 
		fin >> P[i].first >> P[i].second;
	
	sort (P + 1, P + N + 1, cmp);
	
	for (i = 1; i <= N; ++i) 
		for (j = i + 1; j <= N; ++j) {
			double x, y;
			
			x = P[i].first + (P[j].first - P[i].first) * cos(PI / 3) - (P[j].second - P[i].second) * sin(PI / 3);
			y = P[i].second + (P[j].first - P[i].first) * sin(PI / 3) + (P[j].second - P[i].second) * cos(PI / 3);
			rez += cautare(x, y);
			
			x = P[i].first + (P[j].first - P[i].first) * cos(-PI / 3) - (P[j].second - P[i].second) * sin(-PI / 3);
			y = P[i].second + (P[j].first - P[i].first) * sin(-PI / 3) + (P[j].second - P[i].second) * cos(-PI / 3);
			rez += cautare(x, y);
		}
	fout << rez / 3;
	return 0;
}