OI题库

问题描述：

yz住宅小区的未来规划采用了一种新方案：小区由白色的木栅栏围成，栅栏的形状将被设计为一个任意多边形，而每户的住宅就位于多边形的顶点处，多边形的内部则将建成一个优雅怡人的小区公园。

这个方案却给负责小区送报任务的投递员带来了一些麻烦，因为他希望坚持自己的送报习惯：他喜欢骑在自己的自行车上沿着一个标准的圆形路线投送报纸，每当看到自己的右手方向有一户住宅时，他就会将报纸投过去，而且最令他骄傲的是，无论距离远近，他投出的报纸总是准确地落在住户的门前。他的这种极具艺术感的服务方式也正是住户们最感欣赏的地方。

但遗憾的是，他分辨不出每户住宅之间的区别，也记不住每家订了哪些报纸，邮局按照住宅在多边形上的次序把每户的报纸交给他，他就按照这种次序把每户的报纸投送出去。所以图一中的方案是不成立的，因为住户3拿到的总是住户2的报纸，而住户2拿到的报纸却是住户3的。图二中画出了两种可行的方案。

你的任务就是找出所有满足上述要求的投递路线的圆心（这些圆心的坐标应当是整数）。

输入格式(polygon.in)：

输入文件名为polygon.in。文件第1行是4个整数x_min、x_max、y_min、y_max，表示圆心坐标的范围，第2行是一个正整数n(n£100)，表示多边形的顶点数，从第3行至第n+2行是每个顶点的坐标(x,y)，所有坐标值均为整数，坐标的绝对值不大于1000，顶点按顺时针排序。

输出格式(polygon.out)：

输出文件名为polygon.out。文件中共m行（m为你求出的圆心的个数），每行两个整数(x,y)，表示圆心的坐标，坐标应按y递增的次序输出，如果y相等的，应按x递增的次序。