Cod sursa(job #1774477)

Utilizator ArkinyStoica Alex Arkiny Data 8 octombrie 2016 23:53:51
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream>
#include<math.h>
#include<vector>
using namespace std;

ifstream in("trapez.in");

ofstream out("trapez.out");

typedef pair<long long, long long> POINT2D;

POINT2D points[1010];


vector<pair<POINT2D,long long>> H[666013];

long long Abs(long long x)
{
	return (x > 0) ? x : -x;
}

long long get_key(POINT2D p)
{
	return (Abs(p.first) * 2 + Abs(p.second) * 3) % 666013;
}

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

bool compare(POINT2D &p1, POINT2D &p2)
{
	return p1.first==p2.first && p1.second == p2.second;
}

void findH(POINT2D p, long long &r)
{
	for (int i = 0; i < H[get_key(p)].size(); ++i)
		if (compare(p, make_pair(H[get_key(p)][i].first.first, H[get_key(p)][i].first.second)))
		{
			r = H[get_key(p)][i].second;
			H[get_key(p)][i].second++;

			break;
		}
}

int N;




long long cmmdc(long long a, long long b)
{
	while (b)
	{
		long long r = a%b;
		a = b;
		b = r;
	}
	return a;
}

int main()
{

	in >> N;

	for (int i = 1;i <= N;++i)
		in >> points[i].first >> points[i].second;
	long long rez=0;
	for (int i = 1;i <= N;++i)
	{
		for (int j = i+1;j <= N;++j)
		{
			if (points[i].first - points[j].first == 0)
			{
				long long r = -1;
				findH(make_pair(1LL << 50, 1LL << 50), r);
				if (r == -1)
					insert(make_pair(1LL << 50, 1LL << 50));
				else
					rez += r;
			}
			else if (points[i].second - points[j].second == 0)
			{
				long long r = -1;
				findH(make_pair(0, 0), r);
				if (r == -1)
					insert(make_pair(0, 0));
				else
					rez += r;
			}
			else
			{
				long long v_y = points[i].second - points[j].second, v_x = points[i].first - points[j].first;
				long long cm = cmmdc(Abs(v_y), Abs(v_x));
				if (v_y < 0 && v_x < 0)
					v_x *= -1, v_y *= -1;
				else if (v_x < 0 || v_y < 0)
				{
					if (v_x < 0)
						v_y *= -1,v_x*=-1;
				}
				long long r = -1;
				findH(make_pair(v_y/cm, v_x/cm), r);
				if (r == -1)
					insert(make_pair(v_y/cm, v_x/cm));
				else
					rez += r;
			}
		}
	}
	
	out << rez;

	return 0;
}