Cod sursa(job #479160)

Utilizator MirceaTanaseMircea Tanase MirceaTanase Data 23 august 2010 02:10:45
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <algorithm>
#include <stdio.h>
#include <math.h>

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

using namespace std;

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

inline double 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 <int, int> key)
{
	if (fr > ls)
		return 0;
	int med = (fr + ls) / 2;

	if (abs(cInt[med].x - key.x <= 1) && abs(cInt[med].y - key.y) <= 1)
		return 1;
	if (cInt[med].x < key.x || (abs(cInt[med].x - key.x <= 1) && cInt[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);

		cInt[i].x = c[i].x * 100000;
		cInt[i].y = c[i].y * 100000;
	}

	sort(c + 1, c + 1 + n);
	sort(cInt + 1, cInt + 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);
			double A = c[i].y - c[j].y;
			double B = c[j].x - c[i].x;
			double C = -(A * c[i].x + B * c[i].y);

			double d = dist(c[i], c[j]) * sqrt((double) 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
			{
				double ecA = (B * B + A * A) / (A * A);
				double ecB = 2 * (B * C / (A * A) + B * med.x / A - med.y);
				double ecC = -(d * d) + med.x * med.x + med.y * med.y + (C * C) / (A * A) + 2 * C * med.x / A;

				double delta = sqrt((double) ecB * ecB - 4 * ecA * ecC);

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

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

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

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