World Codesprint 10: Node-Point Mappings

https://www.hackerrank.com/contests/world-codesprint-10/challenges/node-point-mappings

解法

一番左の点（複数あるなら下にある方）を根に対応させる。根を中心に偏角ソートし、たとえば部分木のサイズが [4, 5, 3] となっていたら下図のように領域を分割する。

f:id:pekempey:20170502000232p:plain

これを再帰的に繰り返すことでかならず構築できる。

三点が一直線上に並ばないことと、一番左の点を中心にしているため、外積の正負を比較関数にして偏角ソート可能。

#include <iostream>
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
#include <complex>

using P = std::complex<long long>;

long long cross(const P &a, const P &b) {
	return imag(conj(a) * b);
}

std::vector<std::vector<int>> readTree(int n) {
	std::vector<std::vector<int>> tree(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--;
		v--;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	return tree;
}

std::vector<P> readPoints(int n) {
	std::vector<P> points(n);
	for (int i = 0; i < n; i++) {
		long long x, y;
		scanf("%lld %lld", &x, &y);
		points[i].real(x);
		points[i].imag(y);
	}
	return points;
}

int main() {
	int n;
	std::cin >> n;

	auto tree = readTree(n);
	auto points = readPoints(n);

	std::vector<P> map(n);
	std::vector<int> size(n);

	std::function<void(int, int)> dfs = [&](int u, int p) {
		size[u] = 1;
		for (int v : tree[u]) {
			if (v != p) {
				dfs(v, u);
				size[u] += size[v];
			}
		}
	};
	dfs(0, -1);

	std::function<void(int, int, std::vector<P>)> dfs2 = [&](int u, int p, std::vector<P> ps) {
		auto it = min_element(ps.begin(), ps.end(), [&](const P &a, const P &b) {
			return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
		});
		P min = *it;
		ps.erase(it);
		std::sort(ps.begin(), ps.end(), [&](const P &a, const P &b) {
			return cross(a - min, b - min) < 0;
		});
		map[u] = min;

		int k = 0;
		for (int i = 0; i < tree[u].size(); i++) {
			const int v = tree[u][i];
			if (v == p) {
				continue;
			}
			std::vector<P> next;
			for (int j = 0; j < size[v]; j++) {
				next.push_back(ps[k++]);
			}
			dfs2(v, u, next);
		}
	};
	dfs2(0, -1, points);

	for (int i = 0; i < n; i++) {
		int j = std::find(points.begin(), points.end(), map[i]) - points.begin();
		std::cout << j + 1 << " ";
	}
}