Cod sursa(job #479140)

Utilizator MirceaTanaseMircea Tanase MirceaTanase Data 23 august 2010 01:29:47
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <algorithm>
#include <stdio.h>
#include <math.h>

#define eps 0.0001
#define MAX 2048
#define mp make_pair
#define x first
#define y second

using namespace std;

int n, sol;
pair <double, double> c[MAX];

inline float dist(pair <double, double> a, pair <double, double> b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

inline int cautaBin(int fr, int ls, pair <double, double> key)
{
	if (fr > ls)
		return 0;
	int med = (fr + ls) / 2;

	if (fabs(key.x - c[med].x) <= eps && fabs(key.y - c[med].y) <= eps)
		return 1;
	if (c[med].x < key.x || (fabs(key.x - c[med].x) <= eps && c[med].y < key.y))
		return cautaBin(med + 1, ls, key);
	else return cautaBin(fr, med - 1, key);
}

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

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%lf %lf", &c[i].x, &c[i].y);

	sort(c + 1, c + 1 + n);

	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			pair <double, double> med = mp((c[i].x + c[j].x) / 2, (c[i].y + c[j].y) / 2);
			float A = c[i].y - c[j].y;
			float B = c[j].x - c[i].x;
			float C = -(A * c[i].x + B * c[i].y);

			float d = dist(c[i], c[j]) * sqrt((float) 3) / 2;

			swap(A, B);
			A = -A;

			C = -(A * med.x + B * med.y);

			if (!A)
			{
				sol += cautaBin(j + 1, n, mp(med.x - d, med.y));
				sol += cautaBin(j + 1, n, mp(med.x + d, med.y));
			}
			else
			{
				float ecA = (B * B + A * A) / (A * A);
				float ecB = 2 * (B * C / (A * A) + B * med.x / A - med.y);
				float ecC = -(d * d) + med.x * med.x + med.y * med.y + (C * C) / (A * A) + 2 * C * med.x / A;

				double y1 = (-ecB - sqrt((double) ecB * ecB - 4 * ecA * ecC)) / (2 * ecA);
				double x1 = -(B * y1 + C) / A;
				sol += cautaBin(j + 1, n, mp(x1, y1));

				y1 = (-ecB + sqrt((double) ecB * ecB - 4 * ecA * ecC)) / (2 * ecA);
				x1 = -(B * y1 + C) / A;
				sol += cautaBin(j + 1, n, mp(x1, y1));
			}
		}
	}

	printf("%d\n", sol);

	fclose(stdin);
	fclose(stdout);
	return 0;
}