#P3915. [Baltic2014]demarcation

    ID: 3117 传统题 3000ms 256MiB 尝试: 4 已通过: 3 难度: 10 上传者: 标签>CF2900省选/NOI-扫描线有序集合有限候选集缩减一维前缀和二分查找事件同坐标排序坐标变换暴力枚举

[Baltic2014]demarcation

题目描述

给定一个简单多边形,它的各边都水平或竖直,相邻两边互相垂直。除相邻边的公共端点外,任意两条边都不相交或相切。

请用一条水平或竖直的线段将多边形分割为两个全等的多边形。线段的两个端点必须是整数坐标并位于原多边形的边界上,其余部分必须严格位于原多边形内部。允许通过平移、旋转和镜像判断两个多边形是否全等。

输入格式

第一行一个整数 NN(4≤N≤1054\le N\le10^5),表示顶点个数。

接下来 NN 行,每行两个整数 Xi,YiX_i,Y_i(0≤Xi,Yi≤1090\le X_i,Y_i\le10^9),按沿边界的顺序给出各顶点。最后一个顶点与第一个顶点相邻。

输出格式

如果存在可行的切割线段,输出一行四个空格分隔的整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示其两个端点。多解时可输出任意一组。若不存在,输出 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

题目来源