Cod sursa(job #1133698)

Utilizator SmaugSmaug . Smaug Data 5 martie 2014 13:04:24
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

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

template <typename T>
	inline T abs(T a) {
		return max(a, -a);
	}

struct point {
	double x, y;
	bool operator< (const point &b) {
		if (abs(x - b.x) < 0.001)
			return y - b.y < 0;
		return x - b.x < 0;
	}
	bool operator== (const point &b) {
		if (abs(x - b.x) < 0.001 and abs(y - b.y) < 0.001)
			return true;
		return false;
	}
	bool operator() (const point &a, const point &b) const {
		if (abs(a.x - b.x) < 0.001)
			return a.y - b.y < 0;
		return a.x - b.y < 0;
	}
};

inline point rotate(point a, point b) {
	point p;
	p.x = 1.0 / 2.0 * (a.x - b.x) - sqrt(3.0) / 2.0 * (a.y - b.y) + b.x;
	p.y = sqrt(3.0) / 2.0 * (a.x - b.x) + 1.0 / 2.0 * (a.y - b.y) + b.y;
	return p;
}

int n, r;
point a[1505];

int bs(point p) {
	int i = 0, cnt = 1 << 10;
	for (; cnt; cnt >>= 1)
		if (i + cnt <= n and a[i + cnt] < p);
	return a[i + 1] == p;
}

int main() {
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> a[i].x >> a[i].y;
	
	sort(a + 1, a + n + 1, point());

	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			point _1, _2;
			_1 = rotate(a[i], a[j]);
			_2 = rotate(a[j], a[i]);
			r += bs(_1) + bs(_2);
		}
	
	fout << r;
}