[BalticOI 2014 Day2] Demarcation
题目描述
给定一个多边形,求画一条线段将这个多边形分为两个全等的多边形。
需要保证这条线段与坐标轴平行。
输入输出格式
输入格式
第一行一个整数 $N$ 代表这个多边形由 $N$ 个点组成。
接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表多边形的一个点 $(X_i,Y_i)$。
输出格式
如果不可以分为两个全等的多边形,输出一个字符串 `NO`。
如果可以,输出四个整数 $x_1,y_1,x_2,y_2$ 代表线段 $(x_1,y_1)\to (x_2,y_2)$。
输入输出样例
输入样例 #1
10
0 0
1 0
1 1
3 1
3 5
2 5
2 3
1 3
1 2
0 2
输出样例 #1
1 2 3 2
说明
#### 样例说明
对于样例 $1$,如下图所示,可以分成两个全等的多边形:
![](https://cdn.luogu.com.cn/upload/image_hosting/4ueohtd3.png)
同理,输出 `3 2 1 2` 也可。
对于样例 $2$,如下图所示,不可以分为两个全等的多边形:
![](https://cdn.luogu.com.cn/upload/image_hosting/yl64yxp9.png)
#### 数据规模与约定
**本题采用捆绑测试。**
- Subtask 1(12 pts):保证有解。
- Subtask 2(15 pts):$N \le 200$。
- Subtask 3(23 pts):$N \le 2000$。
- Subtask 4(50 pts):无特殊限制。
对于 $100\%$ 的数据,$4 \le N \le 10^5$。
**本题采用 Special Judge。**
#### 说明
翻译自 [BalticOI 2014 Day2 A Demarcation](https://boi.cses.fi/files/boi2014_day2.pdf)。