Cod sursa(job #1776367)

Utilizator ArkinyStoica Alex Arkiny Data 11 octombrie 2016 10:57:07
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;

ifstream in("triang.in");
ofstream out("triang.out");

#define EPS 0.001


typedef pair<double, double> POINT2D;

vector<POINT2D> H[600010];

POINT2D points[2000];

int convert(double x)
{
	int a = x * 1000;
	if (abs(((int)(x * 10000)) % 10) > 5)
	{
		if (x < 0)
			a--;
		else a++;
	}
	return a;
}

long long get_key(POINT2D p)
{

	int a = convert(p.first);
	int b = convert(p.second);
	int h = (a * 2 + b * 3) % 600003;
	if (h < 0)
		h += 600003;
	return h;
}

void insert(POINT2D p)
{
	H[get_key(p)].push_back(p);
}

bool compare(POINT2D &p1, POINT2D &p2)
{
	return fabs(p1.first - p2.first) < EPS && fabs(p1.second - p2.second) < EPS;
}

bool findH(POINT2D p)
{
	for (int i = 0; i < H[get_key(p)].size(); ++i)
		if (compare(p, H[get_key(p)][i]))
			return true;
	return false;
}


int main()
{

	int N;

	in >> N;

	for (int i = 1; i <= N; ++i)
		in >> points[i].first >> points[i].second, insert(POINT2D(points[i].first, points[i].second));
	int nr = 0;
	for (int i = 1; i <= N; ++i)
		for (int j = i + 1; j <= N; ++j)
		{
			double xm = (points[i].first + points[j].first) / 2, ym = (points[i].second + points[j].second) / 2;

			double x1 = 0, y1 = 0, x2 = 0, y2 = 0;

			double distance = (points[j].first - points[i].first)*(points[j].first - points[i].first) + (points[j].second - points[i].second)*(points[j].second - points[i].second);

			double slope = 0;

			if (fabs(points[j].second - points[i].second) < EPS)
			{
				x1 = x2 = xm;
				y1 = ym + sqrt(3.0)*sqrt(distance) / 2;
				y2 = ym - sqrt(3.0)*sqrt(distance) / 2;
			}
			else
			{
				if (fabs(points[j].first - points[i].first) < EPS)
				{
					slope = 0;
				}
				else
				{
					slope = -(points[j].first - points[i].first) / (points[j].second - points[i].second);
				}

				x1 = (2 * xm + sqrt(3 * distance / (slope*slope + 1))) / 2;
				x2 = (2 * xm - sqrt(3 * distance / (slope*slope + 1))) / 2;

				y1 = x1*slope - slope*xm + ym;
				y2 = x2*slope - slope*xm + ym;

			}

			if (findH(POINT2D(x1, y1)) == 1)
				++nr;
			if (findH(POINT2D(x2, y2)) == 1)
				++nr;


		}

	out << nr / 3;

	return 0;
}