Mai intai trebuie sa te autentifici.

Cod sursa(job #1774433)

Utilizator ArkinyStoica Alex Arkiny Data 8 octombrie 2016 22:34:32
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 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<POINT2D> 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(p);
}

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

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 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;

	for (int i = 1;i <= N;++i)
	{
		for (int j = i+1;j <= N;++j)
		{
			if (points[i].first - points[j].first == 0)
			{
				if (!findH(make_pair(1LL << 50, 1LL << 50)))
					insert(make_pair(1LL << 50, 1LL << 50));
			}
			else if (points[i].second - points[j].second == 0)
				if (!findH(make_pair(0, 0)))
					insert(make_pair(0, 0));
			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;
				}
				if (!findH(make_pair(v_y/cm, v_x/cm)))
					insert(make_pair(v_y/cm, v_x/cm));
			}
		}
	}
	

	return 0;
}