Diplomatic License#1046
In an effort to minimize expenses for foreign affairs, it was decided that it is not sufficient for each country to maintain diplomatic relations with only one other country, since, with more than two countries in the world, some countries would not be able to communicate through a chain of diplomats.
Suppose now that each country maintains diplomatic relations with at most two other countries. According to unwritten diplomatic rules, each country is to be treated equally, so every country must maintain diplomatic relations with exactly two other countries.
International topologists have proposed a structure to meet these needs: arrange the countries in a circle so that each country has diplomatic relations with its left and right neighbors. In reality, each country's diplomatic office is located in its own country, and for simplicity, its position is given as a point in a two-dimensional plane. If you connect the diplomatic offices of related countries by straight lines, you will get a polygon.
Now, locations for bilateral diplomatic meetings must be established. For diplomatic reasons, both diplomats must travel equal distances to the meeting location. For efficiency, this travel distance should be minimized. Get ready to solve this problem!
The input contains several test cases. Each test case begins with an integer (N \ge 3), the number of countries, which is always odd. Then follow pairs of integer and coordinates (|x|, |y| < 10^{12}), specifying the locations of the diplomatic offices. The countries are arranged in the order given, and the first country is also a neighbor of the last. Input ends at EOF.
For each test case, output , the number of meeting locations, followed by the and coordinates of each location. The order of the meeting locations should correspond to the input: start with the meeting location for the first two countries and continue in order, finishing with the meeting location for the -th and the first countries. Coordinates should be given to digits after the decimal point.
Example 1
Note that the input and output may be interpreted as polygons. The relationship between the input and output polygons is illustrated in the figure for Problem 1047. Additional input samples can be generated using your solutions to that problem.