#P17804. [Ontak2024]TES
[Ontak2024]TES
题目描述
一个正 边形的顶点按顺时针方向编号为 。相邻顶点之间均有边,包括 。
给定 条内部对角线,它们互不交叉,将整个多边形剖分成三角形。
请在平面上为每个顶点 构造一个边平行于坐标轴、顶点坐标为整数、面积为正的矩形 ,满足:
- 任意两个矩形的内部不相交。
- 与 的边界有正长度的公共线段,当且仅当 是多边形相邻顶点,或输入中存在连接它们的对角线。
仅在一个点接触不算相邻。输出任意满足条件的构造;矩形不必位于原多边形内部。
输入格式
第一行整数 。
接下来 行,每行两个整数 ,表示一条内部对角线。输入保证构成合法三角剖分。
输出格式
输出 行。第 行四个整数 ,依次表示矩形 的左下角和右上角。
必须满足
$$0\le x_1<x_2\le10^{18},\qquad0\le y_1<y_2\le10^{18}.$$数据范围
,,。
样例 1
输入:
3
一种合法输出:
0 0 1 2
1 0 2 1
1 1 2 2
样例 2
输入:
4
2 4
一种合法输出:
2 1 4 2
1 2 3 4
2 4 4 5
3 2 5 4
子任务与部分分
| 编号 | 附加限制 | 分值 |
|---|---|---|
| 1 | 内部对角线组成星形 | 10 |
| 2 | 内部对角线组成一条路径 | 12 |
| 3 | ,三角剖分从所有可能方案中随机选取 | 13 |
| 4 | 11 | |
| 5 | 15 | |
| 6 | 20 | |
| 7 | 无附加限制 | 19 |