Cod sursa(job #395395)

Utilizator blasterzMircea Dima blasterz Data 12 februarie 2010 23:05:39
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
// triang infoarena.ro
// @author: Mircea Dima
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#define eps 1e-6
#define oo 0x3f3f3f3f

#define N 1505

using namespace std;

struct point
{
	double x, y;
	point(){};
	point(double _x, double _y){ x = _x; y = _y;};
};

struct cmp
{
	bool operator()(const point &a, const point &b)const
	{
		if (a.x < b.x && fabs(a.x - b.x) >= eps) return 1; // a.x < b.x
		if (fabs(a.x - b.x) < eps)//a.x == b.x
			if (a.y < b.y && fabs(a.y - b.y) >= eps) return 1;
		return 0;
	}
};
			

point a[N];
int n;

void read()
{
	freopen("triang.in","r",stdin);
	scanf("%d\n", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%lf %lf\n", &a[i].x, &a[i].y);

	sort(a+1, a + n + 1, cmp());
}

inline void getPoints(point P1, point P2, point &R1, point &R2)
// in R1 si R2 returnez pctele
{
	point M( (P1.x + P2.x) / 2.0, (P1.y + P2.y) / 2.0); // mijlocul
	
	double m = P1.y == P2.y ? oo :  - (P1.x - P2.x) / (double) (P1.y - P2.y); 
	double n = M.y - m * M.x;
	// y = mx + n este ecuatia mediatoarei
	
	double a = P2.y - P1.y;
	double b = P1.x - P2.x;
	double c = -(a * P1.x + b * P1.y);
	// ax + by + c = 0 este ecuatia dreptei P1 P2
	
	double d = sqrt( (P2.x - P1.x) * (P2.x - P1.x) + (P2.y - P1.y) * (P2.y - P1.y));
	// d = lungimea laturei triunghiului
	
	double h = d * sqrt(3) / 2.0;
	// h = inaltimea
	
	R1.x = a + m * b == 0 ? oo : (h * sqrt(a * a + b * b) - n * b - c) / (a + m * b);
	R1.y = m * R1.x + n;
	
	R2.x = a + m * b == 0 ? oo : (-h * sqrt(a * a + b * b) - n * b - c) / (a + m * b);
	R2.y = m * R2.x + n;	
}

void solve()
{	
	int i, j;
	
	point P1, P2;
	
	int nr = 0;
	
	for (i = 1; i < n; ++i)
		for (j = i + 1; j <= n; ++j)
		{
			getPoints(a[i], a[j], P1, P2);
			
			if (binary_search(a + j + 1, a + n + 1, P1, cmp()) == true)
				++nr;
			
			if (binary_search(a + j + 1, a + n + 1, P2, cmp()) == true)
				++nr;
			
		}
	
		printf("%d\n", nr);
	
}

int main()
{
	freopen("triang.out","w",stdout);
	read();
	solve();
	
	return 0;
}