Submission #698448

#TimeUsernameProblemLanguageResultExecution timeMemory
698448vjudge1Drawing (CEOI22_drawing)C++14
100 / 100
237 ms31108 KiB
// CEOI 2022 Day2 Drawing #include <bits/stdc++.h> using namespace std; typedef long long LL; struct Point { int x, y, id; bool operator<(const Point& p) const { if (x != p.x) return x < p.x; return y < p.y; } }; LL cross(const Point& a, const Point& b, const Point& c) { // cross of a→b, a→c LL x1 = b.x - a.x, y1 = b.y - a.y, x2 = c.x - a.x, y2 = c.y - a.y; return x1 * y2 - x2 * y1; } int main() { ios::sync_with_stdio(false), cin.tie(0); int N; cin >> N; vector<vector<int>> G(N + 1); for (int i = 1, a, b; i < N; i++) cin >> a >> b, G[a].push_back(b), G[b].push_back(a); vector<Point> ps(N); for (int i = 0; i < N; i++) cin >> ps[i].x >> ps[i].y, ps[i].id = i + 1; sort(begin(ps), end(ps)); // O=ps[0] 变成最左下方的点O auto pi = begin(ps); nth_element(pi, pi + 1, end(ps)); sort(pi + 1, end(ps), // 以O为原点, 所有按照极坐标逆时针排序 [&](const Point& a, const Point& b) { return cross(ps[0], a, b) >= 0; }); vector<int> Ans(N + 1); function<void(int, int)> dfs = [&](int u, int fa) { Ans[u] = pi->id, pi++; for (int v : G[u]) if (v != fa) dfs(v, u); }; dfs(1, 0); for (int i = 1; i <= N; i++) printf("%d ", Ans[i]); puts(""); return 0; } // AC 100
#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...