Pagini recente » Cod sursa (job #1098309) | Cod sursa (job #687502) | Cod sursa (job #2343594) | Cod sursa (job #3270830) | Cod sursa (job #2771518)
#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;
}