Cod sursa(job #1082009)

Utilizator vld7Campeanu Vlad vld7 Data 14 ianuarie 2014 00:53:46
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

ifstream f("triang.in");
ofstream g("triang.out");

const double EPS = 0.001;
const double sqrt3 = 1.73205081;

int n, ans;
vector < pair <double, double> > Point;
pair <double, double> P;

bool isEqual (double a, double b) {
	if (abs (a - b) < EPS)
		return 1;
	return 0;
}

bool binsearch (int lo, int hi) {
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (isEqual (Point[mid].x, P.x)) {
			if (isEqual (Point[mid].y, P.y))
				return 1;
			else if (Point[mid].y < P.y)
				lo = mid + 1;
			else
				hi = mid - 1;
		} else if (Point[mid].x < P.x)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	
	return 0;
}

int main() {
	f >> n;
	for (int i = 1; i <= n; i++) {
		double tmp1, tmp2;
		f >> tmp1 >> tmp2;
		Point.push_back (make_pair (tmp1, tmp2));
	}
	
	sort (Point.begin(), Point.end());
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			double x = Point[i].x + Point[i].y * sqrt3 + Point[j].x - Point[j].y * sqrt3;
			double y = -Point[i].x * sqrt3 + Point[i].y + Point[j].y + Point[j].x * sqrt3;
			x /= (double)2;
			y /= (double)2;
			P = make_pair (x, y);
			
			if (binsearch (0, n - 1))
				ans++;
			
			
			x = Point[i].x + Point[j].x + (Point[j].y - Point[i].y) * sqrt3;
			y = Point[i].x * sqrt3 + Point[j].y + Point[i].y - Point[j].x * sqrt3;
			x /= (double)2;
			y /= (double)2;
			P = make_pair (x, y);
			
			if (binsearch (0, n - 1))
				ans++;
		}
		
	g << ans / 3;
	return 0;
}