Cod sursa(job #801438)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 24 octombrie 2012 13:00:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

struct pct {
	double x, y;
};

const int N = 1510;
const double eps = 0.001;

int n, nr;
double r3;
pct p[N];

inline double m(double q) {return q > 0 ? q : -q;}

bool cmp(pct a, pct b) {
	if(m(a.x - b.x) < eps)
		return a.y < b.y;
	return a.x < b.x;
}

bool caut(double x, double y, int i) {
	int pas = 1<<12;

	for(; pas; pas>>=1)
		if(i + pas <= n && p[i + pas].x <= x + eps && p[i + pas].y <= y + eps)
			i += pas;

	return (m(p[i].x - x) <= eps && m(p[i].y - y) <= eps);
}

int main() {
	int i, j, nx, ny;

	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);

	cin >> n;

	for(i = 1; i<=n; ++i)
		cin >> p[i].x >> p[i].y;

	sort(p + 1, p + n + 1, cmp);

	r3 = sqrt(3);

	for(i = 1; i!=n; ++i)
		for(j = i + 1; j<=n; ++j) {

            nx = (p[i].x + p[j].x)/2 - r3/2*(p[j].y - p[i].y);
            ny = (p[i].y + p[j].y)/2 + r3/2*(p[j].x - p[i].x);

			if(caut(nx, ny, j + 1))
				++nr;


            nx = (p[i].x + p[j].x)/2 + r3/2*(p[j].y - p[i].y);
            ny = (p[i].y + p[j].y)/2 - r3/2*(p[j].x - p[i].x);


			if(caut(nx, ny, j + 1))
				++nr;
		}
	cout << nr;

	return 0;
}