Diplomatic License

In an effort to minimize the expenses of foreign affairs, the countries of the world reasoned as follows. It is not enough for each country to maintain diplomatic relations with at most one other country: since there are more than two countries in the world, some pairs of countries would then be unable to communicate with each other through any chain of diplomats.

So assume instead that each country maintains diplomatic relations with at most two other countries. It is an unwritten diplomatic rule that every country must be treated equally, so in fact each country maintains diplomatic relations with exactly two other countries.

Topologists proposed a structure that fits these needs: arrange the countries around a circle and let each country have diplomatic relations with its left and right neighbours. The Foreign Office of every country is located in its capital; for simplicity, assume it is a point in the two-dimensional plane. Connecting the Foreign Offices of diplomatically related countries by straight lines yields a polygon.

It now remains to choose a location for each bilateral diplomatic meeting. For diplomatic reasons, both diplomats must travel equal distances to the meeting location, and for efficiency that distance must be as small as possible. Determine every meeting location.

The input contains several test cases. Each test case starts with the number $n$ of countries involved. You may assume that $n \ge 3$ is odd. Then follow $n$ pairs of $x$- and $y$-coordinates giving the locations of the Foreign Offices. Every coordinate is an integer whose absolute value is less than $10^{12}$. The countries are given in the order in which they sit around the circle; in addition, the first country is a neighbour of the last country in the list. The input is terminated by end of file.

For each test case, output the number of meeting locations (which equals $n$), followed by the $x$- and $y$-coordinate of each location. The meeting locations must appear in the same order as the input: start with the meeting location for the first and second countries, continue through the consecutive pairs, and finally output the meeting location for the $n$-th and the first country. Print every coordinate with exactly six digits after the decimal point.

Note that the meeting locations, taken in input order, can themselves be read as a polygon. Computing the meeting locations from the countries and reconstructing the countries from the meeting locations are inverse problems.