[CEOI 2022] Drawing

Luogu
IDLGP8999
Time1500ms
Memory512MB
DifficultyP7
2022Special JudgeCEOI(中欧)
给定平面上的 $N$ 个点,和一棵大小为 $N$ 的树 $T$,保证这棵树上每个点的度数至多为 $3$,树上节点按 $1\sim N$ 编号。 你需要为平面上的点使用 $1\sim N$ 的编号重编号之后,对于所有树上的边 $e=(u,v)$,将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后,任意两条线段除了在端点上相交没有其他的相交点。 试构造一组方案,保证一定有解。 ## Input 第一行一个整数 $N$。 接下来 $N-1$ 行,一行两个整数 $a,b$,表示有一条从 $a$ 连向 $b$ 的边。 接下来 $N$ 行,一行两个整数 $x,y$,表示一个点的横纵坐标为 $(x,y)$。保证这 $N$ 个点两两不同,且没有任意三点共线。 ## Output 输出一行 $N$ 个整数,第 $i$ 个数应为原本的第 $i$ 个点的标号。 [samples] ## Note ### 样例 3 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/1sz6z9sk.png) 蓝色数字表示所分配的编号,黑色数字表示原本的编号。 ### 数据规模与约定 对于所有数据,保证 $0\le x,y\le 10^9$。 | Subtask 编号 | 特殊限制 | 分数 | | :----------: | :--------------------------------------: | :--: | | $1$ | $3\le N\le 2\times 10^5$,所有点均在凸包上 | $10$ | | $2$ | $1\le N\le 4000$ | $15$ | | $3$ | $1\le N\le 10^4$ | $15$ | | $4$ | $1\le N\le 8\times 10^4$ | $35$ | | $5$ | $1\le N\le 2\times 10^5$ | $25$ |
Samples
Input #1
3
1 2
2 3
10 10
10 20
20 10
Output #1
1 2 3
Input #2
5
1 2
1 3
1 4
4 5
10 10
10 30
30 10
30 30
20 25
Output #2
5 4 2 3 1
Input #3
6
1 2
2 3
1 4
4 5
4 6
10 60
10 40
40 50
40 30
70 30
70 10
Output #3
6 5 4 1 2 3
API Response (JSON)
{
  "problem": {
    "name": "[CEOI 2022] Drawing",
    "description": {
      "content": "给定平面上的 $N$ 个点,和一棵大小为 $N$ 的树 $T$,保证这棵树上每个点的度数至多为 $3$,树上节点按 $1\\sim N$ 编号。 你需要为平面上的点使用 $1\\sim N$ 的编号重编号之后,对于所有树上的边 $e=(u,v)$,将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后,任意两条线段除了在端点上相交没有其他的相交点。 试构造一组方案,保证一定有解。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8999"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定平面上的 $N$ 个点,和一棵大小为 $N$ 的树 $T$,保证这棵树上每个点的度数至多为 $3$,树上节点按 $1\\sim N$ 编号。\n\n你需要为平面上的点使用 $1\\sim N$ 的编号重编号之后,对于所有树上的边 $e=(u,v)$,将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后,任意两条线段除了在端点上相交没有其他的相交点。\n\n试构造一组方案,保证一定有解。\n\n## Inp...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments