Submission #1227513

#TimeUsernameProblemLanguageResultExecution timeMemory
1227513spetrDrawing (CEOI22_drawing)C++20
0 / 100
69 ms12464 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...