Description

The future plan of the YZ residential community adopts a new scheme: the community will be enclosed by a white wooden fence whose shape is designed as an arbitrary polygon. Each household is located at a vertex of the polygon, while the interior of the polygon will be built into an elegant and pleasant community park.

This plan, however, causes some trouble for the deliveryman responsible for delivering newspapers to the community, because he insists on his delivery habit: he likes to ride his bicycle along a perfect circular route to deliver newspapers. Whenever he sees a household on his right-hand side, he throws a newspaper to it, and what makes him proud is that, regardless of distance, his throw always lands exactly at the household’s doorstep. This artistic service is precisely what the residents appreciate most.

Unfortunately, he cannot tell households apart and cannot remember which newspapers each family subscribes to. The post office hands him the newspapers in the order of the residences along the polygon, and he delivers them in that same order. Therefore, the plan in Figure 1 is invalid, because resident 3 always receives resident 2’s newspaper, while resident 2 receives resident 3’s newspaper. Figure 2 shows two feasible plans.

Your task is to find all centers of circular routes that satisfy the above requirements (these centers must have integer coordinates).

Input Format

• The first line contains four integers Xmin, Xmax, Ymin, Ymax, specifying the search range for the circle center coordinates.
• The second line contains a positive integer $n$ ($n \le 100$), the number of vertices of the polygon.
• The next $n$ lines (lines 3 to $n+2$) each contain two integers $x$ and $y$, the coordinates of a vertex. All coordinates are integers with absolute value at most $1000$. The vertices are given in clockwise order.

Output Format

Output $m$ lines, where $m$ is the number of centers you find. Each line contains two integers $x$ and $y$, representing a circle center. The centers must be output in order of increasing $y$; if $y$ is the same, order by increasing $x$.

-10 10 -10 10
7
-4 -6
-4 0
0 0
-2 4
6 5
4 2
8 0

1 -1

Hint

Translated by ChatGPT 5