Cod sursa(job #2771518)

Utilizator Alin_StanciuStanciu Alin Alin_Stanciu Data 27 august 2021 19:52:12
Problema Overlap Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.75 kb
#define MAX_N 800

#include <iostream>
#include <fstream>
#include <map>

using namespace std;

ifstream fin("overlap.in");
ofstream fout("overlap.out");

struct point
{
	int x, y;

	bool operator < (const point& other) const
	{
		return x < other.x || (x == other.x && y < other.y);
	}

} A[MAX_N + 1], B[MAX_N + 1], C[MAX_N + 1];

struct coord_data
{
	int posib_nerot, posib_rot, sigur_nerot, sigur_rot;
	point nerot_to_rot, rot_to_nerot;
};

int n;

bool Check();
bool SolveCoord(coord_data&, map<point, coord_data>&);
bool Enpair(coord_data&, int, map<point, coord_data>&);

int main()
{
	fin >> n;

	for (int i = 1; i <= n; ++i)
	{
		fin >> A[i].x >> A[i].y;
		B[i] = A[i];
	}

	for (int i = 1; i <= 4; ++i)
	{
		for (int j = 2; j <= n; ++j)
		{
			// A[1] - corespondend cu B[j].

			int dx = B[j].x - A[1].x, dy = B[j].y - A[1].y;

			for (int k = 1; k <= n; ++k)
			{
				C[k].x = B[k].x - dx;
				C[k].y = B[k].y - dy;
			}

			if (Check())
				return 0;
		}

		// Rotatie.
		for (int j = 1; j <= n; ++j)
		{
			swap(B[j].x, B[j].y);
			B[j].x = -B[j].x;
		}
	}

	return 0;
}

bool Check()
{
	// Pentru fiecare coordonate (x, y) tin minte cate puncte am acolo nerotite si rotite.
	map<point, coord_data> M;

	for (int i = 1; i <= n; ++i)
	{
		++M[A[i]].posib_nerot;
		M[A[i]].nerot_to_rot = C[i];
		++M[C[i]].posib_rot;
		M[C[i]].rot_to_nerot = A[i];
	}

	for (auto& el : M)
	{
		coord_data& data = el.second;

		if (!SolveCoord(data, M))
			return false;
	}

	// Daca am ajuns aici mai am doar ciclurile de rezolvat.

	for (auto& el : M)
	{
		coord_data& data = el.second;

		if (data.posib_nerot > 0) // Ar trebui ca data.posib_nerot == data.posib_rot
		{
			Enpair(data, data.posib_nerot, M);
		}
	}

	// Daca am ajuns aici am gasit o solutie si o afisez.

	for (int i = 1; i <= n; ++i)
	{
		if (M[A[i]].sigur_nerot > 0)
		{
			fout << 1 << '\n';
			--M[A[i]].sigur_nerot;
		}
		else if (M[C[i]].sigur_rot > 0)
		{
			fout << 2 << '\n';
			--M[C[i]].sigur_rot;
		}
	}
}

bool SolveCoord(coord_data& data, map<point, coord_data>& M)
{
	if (data.posib_nerot > data.posib_rot) // Daca am mai multe puncte nerotite inseamna ca sigur nu au pereche toate punctele nerotite, deci o parte sunt 100% rotite.
	{
		int delta = data.posib_nerot - data.posib_rot;

		if (!Enpair(M[data.nerot_to_rot], delta, M)) // Imperechez cele 'delta' puncte rotite, corespondentele celor 'delta' nerotite care stiu ca nu si-ar fi gasit pereche.
			return false;
	}

	else if (data.posib_rot > data.posib_nerot) // Daca am mai multe puncte rotite inseamna ca sigur nu au pereche toate punctele rotite, deci o parte sunt 100% nerotite.
	{
		int delta = data.posib_rot - data.posib_nerot;

		if (!Enpair(M[data.rot_to_nerot], delta, M)) // Imperechez cele 'delta' puncte nerotite, corespondentele celor 'delta' rotite care stiu ca nu si-ar fi gasit pereche.
			return false;
	}
}

bool Enpair(coord_data& data, int count, map<point, coord_data>& M)
{
	// La coordonatele descrise de 'data' vreau sa imperechez 'count' puncte.
	data.sigur_nerot += count;
	data.sigur_rot += count;
	data.posib_nerot -= count;
	data.posib_rot -= count;

	coord_data& cor_nerot = M[data.nerot_to_rot]; // Corespondentul rotit al punctului nerotit.
	cor_nerot.posib_rot -= count;

	coord_data& cor_rot = M[data.rot_to_nerot]; // Corespondentul nerotit al punctului rotit.
	cor_rot.posib_nerot -= count;

	if (data.posib_nerot < 0 || data.posib_rot < 0 || cor_nerot.posib_rot < 0 || cor_rot.posib_nerot < 0)
		return false;

	// Continui sa fac verificari pe coordonatele schimbate.
	if (!SolveCoord(data, M)) return false;
	if (!SolveCoord(cor_nerot, M)) return false;
	if (!SolveCoord(cor_rot, M)) return false;
}