#P3915. [Baltic2014]demarcation
[Baltic2014]demarcation
题目描述
给定一个简单多边形,它的各边都水平或竖直,相邻两边互相垂直。除相邻边的公共端点外,任意两条边都不相交或相切。
请用一条水平或竖直的线段将多边形分割为两个全等的多边形。线段的两个端点必须是整数坐标并位于原多边形的边界上,其余部分必须严格位于原多边形内部。允许通过平移、旋转和镜像判断两个多边形是否全等。
输入格式
第一行一个整数 (),表示顶点个数。
接下来 行,每行两个整数 (),按沿边界的顺序给出各顶点。最后一个顶点与第一个顶点相邻。
输出格式
如果存在可行的切割线段,输出一行四个空格分隔的整数 ,表示其两个端点。多解时可输出任意一组。若不存在,输出 NO。
样例
10
0 0
1 0
1 1
3 1
3 5
2 5
2 3
1 3
1 2
0 2
1 2 3 2
6
0 0
1 0
1 1
2 1
2 2
0 2
NO