Cod sursa(job #2758603)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 11 iunie 2021 15:52:32
Problema Overlap Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <map>

using namespace std;

const int NMAX = 800;
int N;

int x[NMAX], y[NMAX];
const int sin[]{0, 1, 0, -1};
const int cos[]{1, 0, -1, 0};
int where[NMAX];
map<pair<int, int>, int> pts;


int main() {
	ifstream in("overlap.in");
	ofstream out("overlap.out");

	in >> N;

	for (int i = 0; i < N; i++) {
		in >> x[i] >> y[i];
		pts[{x[i], y[i]}] = i;
	}

	for (int i = 1; i < N; i++) {
		// p[0] -> p[i]
		
		for (int a = 0; a < 4; a++) {
			int xr = cos[a] * x[0] - sin[a] * y[0];
			int yr = sin[a] * x[0] + cos[a] * y[0];

			int dx = x[i] - xr;	
			int dy = y[i] - yr;	

			int pairs = 0;

			memset(where, 0, sizeof(where));

			for (int j = 0; j < N; j++) {
				if (where[j]) continue;

				int xd = cos[a] * x[j] - sin[a] * y[j] + dx;
				int yd = sin[a] * x[j] + cos[a] * y[j] + dy;

				// Caut (xd, yd)
				auto it = pts.find({xd, yd});
				if (it == pts.end()) continue;

				int k = it->second;
				++pairs;
				where[j] = 1;
				where[k] = 2;
			}

			if (pairs == N/2) {
				for (int i = 0; i < N; i++)
					out << where[i] << '\n';
				return 0;
			}
		}
	}
}