Submission #698448

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
698448	2023-02-13 13:43:01	vjudge1	Drawing (CEOI22_drawing)	C++14	100 / 100	237 ms	31108 KiB

Main

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
// 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; });
  
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 35 / 35
• Subtask 5: 25 / 25