Cod sursa(job #1247519)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 22 octombrie 2014 21:54:51
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define DIM 1505
#define eps 0.001
#define infile "triang.in"
#define outfile "triang.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

struct point {
	double x;
	double y;
} A[DIM];

int n;

bool cmp(const point &a, const point &b) {
	return (a.x == b.x ? a.y < b.y : a.x < b.x);
}

bool exists(int st, int dr, double x, double y) {
	while (st <= dr) {
		int mid = (st + dr) / 2;
		if ((-eps < A[mid].x - x && A[mid].x - x < eps) && (-eps < A[mid].y - y && A[mid].y - y < eps))
			return 1;
		if (A[mid].x < x) {
			st = mid + 1;
			continue;
		}
		if (A[mid].x > x) {
			dr = mid - 1;
			continue;
		}
		if (A[mid].y < y) {
			st = mid + 1;
			continue;
		}
		if (A[mid].y >= y) {
			dr = mid - 1;
			continue;
		}
	}
	return 0;
}

int main() {
	f >> n;
	for (int i = 1; i <= n; ++i)
		f >> A[i].x >> A[i].y;
	std::sort(A + 1, A + n + 1, cmp);
	
	double sqrt3 = sqrt(3.0);
	int SOL = 0;
	
	for (int i = 1; i < n - 1; ++i)
		for (int j = i + 1; j < n; ++j) {
		if (exists(j + 1, n, (A[i].x + A[j].x) / 2 + sqrt3*(A[i].y - A[j].y) / 2, (A[i].y + A[j].y) / 2 + sqrt3*(A[j].x - A[i].x) / 2))
				++SOL;
		if (exists(j + 1, n, (A[i].x + A[j].x) / 2 + sqrt3*(A[j].y - A[i].y) / 2, (A[i].y + A[j].y) / 2 + sqrt3*(A[i].x - A[j].x) / 2))
				++SOL;
		}
	g << SOL;
	return 0;
}

//Trust me, I'm the Doctor!