#P18768. Homework Of Xenia
Homework Of Xenia
Homework Of Xenia
Xenia正在大学学习离散代数拓扑几何,但她缺了很多节课。作为惩罚,老师给她布置了下面的作业。
给定平面图 ,请将它嵌入 :所有顶点对应的点必须两两不同,所有坐标的绝对值不超过 ,每条边对应连接其两个端点的线段,且所有边的长度相等。嵌入后的线段允许相交。
帮助Xenia完成作业。
输入格式
第一行包含两个整数 ,分别表示顶点数和边数:
接下来 行,每行两个整数 (),表示一条无向边。
保证输入图是平面图,没有自环和重边。
输出格式
如果无法嵌入,输出一个整数 。
否则输出 行,第 行给出对应顶点的10个整数坐标 ,满足 ,并且所有顶点的坐标向量两两不同。
必须存在同一个正数 ,使得输入中每条边 都满足
$$\operatorname{dist}(c_u,c_v)=d,\qquad \operatorname{dist}(c_u,c_v)=\sqrt{\sum_{j=1}^{10}(c_{u,j}-c_{v,j})^2}.$$不同连通分量的边也必须共用同一个 。没有边的顶点对不受距离条件限制;当 时,只需满足坐标范围和顶点两两不同。答案可能不唯一,输出任意合法方案。
样例
样例1
输入:
2 1
1 2
输出(其中一种合法方案):
0 0 0 0 0 0 0 0 0 0
0 5 7 0 1 7 9 0 2 0
样例2
输入:
4 6
1 2
2 3
2 4
3 4
1 3
1 4
输出(其中一种合法方案):
0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0