#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
vl ans;
ll pocet = 0;
vector<pair<double, ll>> uhly;
vll graf;
void dfs(ll v, ll p){
ll c = 0;
for (ll i = 0; i < graf[v].size(); i++){
if (graf[v][i] != p){
dfs(graf[v][i], v);
c++;
}
if (c == 1){
ans[v] = uhly[pocet].second;
pocet++;
}
}
if (c == 0){
ans[v] = uhly[pocet].second;
pocet++;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
graf.resize(n);
for (ll i = 0; i < n-1; i++){
ll a,b;
cin >> a >> b;
a--; b--;
graf[a].push_back(b);
graf[b].push_back(a);
}
vector<pl> body;
for (ll i = 0; i < n; i++){
ll a,b;
cin >> a >> b;
body.push_back({a,b});
}
//Kořen
ll root = 0;
while (graf[root].size() != 1){
root++;
}
ll c_x = body[root].first;
ll c_y = body[root].second;
for (ll i = 1; i < n; i++){
ll x = body[i].first;
ll y = body[i].second;
ll dy = c_x-x;
ll dx = c_y-y;
double uhel = atan2(dy,dx);
uhly.push_back({uhel, i});
}
ans.resize(n, -1);
sort(uhly.begin(), uhly.end());
dfs(root, -1);
ans[0] = root;
for (ll i = 0; i < n; i++){
cout << ans[i] + 1 << " ";
}
return 0;
}
# | 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... |