#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct Point {
int x, y;
} puncte[N];
int area(Point a, Point b, Point c) {
return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x) / 2;
}
bool clockwise(Point a, Point b, Point c) {
return area(a, b, c) > 0;
}
vector<int> vec[N];
vector<int> rvec[N];
int sz[N], ans[N];
void dfsz(int nod, int papa) {
sz[nod] = 1;
for (auto i : vec[nod])
if (i != papa) {
dfsz(i, nod);
sz[nod] += sz[i];
rvec[nod].push_back(i);
}
}
void solve(int root, int loc, vector<int> points) {
ans[loc] = root;
if (rvec[root].size() == 0) {
return;
} else if (rvec[root].size() == 1) {
nth_element(points.begin(), points.begin(), points.end(), [&] (int a, int b) {
if (a == loc || b == loc)
return b != loc;
return clockwise(puncte[loc], puncte[a], puncte[b]);
});
nth_element(points.begin() + 1, points.begin() + 1, points.end(), [&] (int a, int b) {
if (a == loc || b == loc)
return b != loc;
return clockwise(puncte[loc], puncte[a], puncte[b]);
});
vector<int> npoints;
for (int i = 1; i < points.size(); i ++)
npoints.push_back(points[i]);
solve(rvec[root][0], points[1], npoints);
} else {
nth_element(points.begin(), points.begin(), points.end(), [&] (int a, int b) {
if (a == loc || b == loc)
return b != loc;
return clockwise(puncte[loc], puncte[a], puncte[b]);
});
nth_element(points.begin() + 1, points.begin() + 1, points.end(), [&] (int a, int b) {
if (a == loc || b == loc)
return b != loc;
return clockwise(puncte[loc], puncte[a], puncte[b]);
});
nth_element(points.begin() + 2, points.begin() + 1 + sz[rvec[root][0]], points.end(), [&] (int a, int b) {
if (a == loc || b == loc)
return b != loc;
return clockwise(puncte[loc], puncte[a], puncte[b]);
});
vector<int> npoints1;
for (int i = 1; i <= sz[rvec[root][0]]; i ++)
npoints1.push_back(points[i]);
vector<int> npoints2;
for (int i = sz[rvec[root][0]] + 1; i < points.size(); i ++)
npoints2.push_back(points[i]);
solve(rvec[root][0], points[1], npoints1);
solve(rvec[root][1], points[sz[rvec[root][0]] + 1], npoints2);
}
}
signed main() {
int n;
cin >> n;
if (n == 1) {
cout << "1\n";
return 0;
}
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
int root = 0;
for (int i = 1; i <= n; i ++)
if ((int)vec[i].size() == 1)
root = i;
vector<int> nodes;
for (int i = 1; i <= n; i ++) {
cin >> puncte[i].x >> puncte[i].y;
nodes.push_back(i);
}
dfsz(root, 0);
int xmin = 1e9 + 1, loc = 0;
for (int i = 1; i <= n; i ++)
if (puncte[i].x < xmin) {
xmin = puncte[i].x;
loc = i;
}
solve(root, loc, nodes);
for (int i = 1; i <= n; i ++)
cout << ans[i] << " ";
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |