P8999 [CEOI 2022] Drawing
题目描述
给定平面上的 $N$ 个点，和一棵大小为 $N$ 的树 $T$，保证这棵树上每个点的度数至多为 $3$，树上节点按 $1\sim N$ 编号。
你需要为平面上的点使用 $1\sim N$ 的编号重编号之后，对于所有树上的边 $e=(u,v)$，将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后，任意两条线段除了在端点上相交没有其他的相交点。
试构造一组方案，保证一定有解。
输入格式
无
输出格式
无
说明/提示
### 样例 3 解释
蓝色数字表示所分配的编号，黑色数字表示原本的编号。
### 数据规模与约定
对于所有数据，保证 $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$ |