Cod sursa(job #1773364)

Utilizator ArkinyStoica Alex Arkiny Data 7 octombrie 2016 19:28:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<fstream>
#include<algorithm>
#include<unordered_map>
#include<math.h>
#include<vector>
using namespace std;

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

#define EPS 0.01

#define x first
#define y second



typedef pair<long double, long double> POINT2D;

vector<POINT2D> H[600010];

POINT2D points[2000];


int get_key(POINT2D p)
{
	return (long long)(floor(p.x)*floor(p.y)) % 600000;
}

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

bool compare(POINT2D p1, POINT2D p2)
{
	return fabs(p1.x - p2.x) < EPS && fabs(p1.y - p2.y) < 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].x >> points[i].y, insert(POINT2D(points[i].x, points[i].y));
	int nr = 0;
	for (int i = 1;i <= N;++i)
		for (int j = i + 1;j <= N;++j)
		{
			long double xm=(points[i].x + points[j].x)/2, ym = (points[i].y + points[j].y) / 2;

			long double x1, y1, x2, y2;

			long double distance = (points[j].x - points[i].x)*(points[j].x - points[i].x) + (points[j].y - points[i].y)*(points[j].y - points[i].y);

			long double slope;
			
			if (fabs(points[j].y - points[i].y) < EPS)
			{
				x1 = x2 = xm;
				y1 = ym + sqrt(3)*sqrt(distance) / 2;
				y2 = ym - sqrt(3)*sqrt(distance) / 2;
			}
			else
			{
				if (fabs(points[j].x - points[i].x) < EPS)
				{
					slope = 0;
				}
				else
				{
					slope = (points[j].y - points[i].y) / (points[j].x - points[i].x);
					slope = -1 / slope;
				}

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

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

			}

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

			
		}

	out << nr;

	return 0;
}