ComplexCode/cf28a.cpp at master · Mithril0rd/ComplexCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>

using namespace std;

const int MAX_N = 507;

struct Point {
	int x, y;
};

int n, m;
Point nail[MAX_N];
int len[MAX_N], ans[MAX_N];
bool vis[MAX_N];

int dist(int i, int j) {
	return abs(nail[i].x - nail[j].x) + abs(nail[i].y - nail[j].y);
}

bool check(int i, int j) {
	return len[j] == dist(i - 1, i) + dist(i, i + 1);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &nail[i].x, &nail[i].y);
	}
	nail[0] = nail[n], nail[n + 1] = nail[1];
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &len[i]);
	}
	bool no = false;
	memset(ans, -1, sizeof ans);
	for (int i = 1; i <= n; i += 2) {
		bool f = false;
		for (int j = 1; j <= m; ++j) {
			if (!vis[j] && check(i, j)) {
				vis[j] = true;
				ans[i] = j;
				f = true;
				break;
			}
		}
		if (!f) {
			no = true;
			break;
		}
	}
	if (!no) {
		puts("YES");
		for (int i = 1; i <= n; ++i) {
			if (~ans[i]) printf("%d ", ans[i]);
			else printf("-1 ");
		}
	} else {
		memset(vis, false, sizeof vis);
		memset(ans, -1, sizeof ans);
		for (int i = 2; i <= n; i += 2) {
			bool f = false;
			for (int j = 1; j <= m; ++j) {
				if (!vis[j] && check(i, j)) {
					vis[j] = true;
					ans[i] = j;
					f = true;
					break;
				}
			}
			if (!f) {
				puts("NO");
				return 0;
			}
		}
		puts("YES");
		for (int i = 1; i <= n; ++i) {
			if (~ans[i]) printf("%d ", ans[i]);
			else printf("-1 ");
		}
	}
	puts("");
	return 0;
}