#P17804. [Ontak2024]TES

[Ontak2024]TES

题目描述

一个正 nn 边形的顶点按顺时针方向编号为 1,2,…,n1,2,\ldots,n。相邻顶点之间均有边,包括 (n,1)(n,1)。

给定 n−3n-3 条内部对角线,它们互不交叉,将整个多边形剖分成三角形。

请在平面上为每个顶点 ii 构造一个边平行于坐标轴、顶点坐标为整数、面积为正的矩形 RiR_i,满足:

  1. 任意两个矩形的内部不相交。
  2. RiR_i 与 RjR_j 的边界有正长度的公共线段,当且仅当 i,ji,j 是多边形相邻顶点,或输入中存在连接它们的对角线。

仅在一个点接触不算相邻。输出任意满足条件的构造;矩形不必位于原多边形内部。

输入格式

第一行整数 nn。

接下来 n−3n-3 行,每行两个整数 v,uv,u,表示一条内部对角线。输入保证构成合法三角剖分。

输出格式

输出 nn 行。第 ii 行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,依次表示矩形 RiR_i 的左下角和右上角。

必须满足

$$0\le x_1<x_2\le10^{18},\qquad0\le y_1<y_2\le10^{18}.$$

数据范围

3≤n≤10000003\le n\le1000000,1≤u,v≤n1\le u,v\le n,u≠vu\ne v。

样例 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 n≤500n\le500,三角剖分从所有可能方案中随机选取 13
4 n≤6n\le6 11
5 n≤500n\le500 15
6 n≤100000n\le100000 20
7 无附加限制 19