Mexico City is built in a beautiful valley known as the Valley of Mexico which, years ago, was mostly a lake. Around the year 1300, Aztec religious leaders decreed that the lake's center be filled in order to build the capital of their empire. Today, the lake is completely covered.
Before the Aztecs arrived, c cities were located around the lake on its shores. Some of these cities established commercial agreements. Goods were traded, using boats, between cities that had a commercial agreement. It was possible to connect any two cities by a line segment through the lake.
Eventually, the kings of the cities decided to organize this commerce. They designed a commerce route that connected every city around the lake. The route met the following requirements:
The figure below shows the lake and the cities around it. The lines (both * and -) represent commercial agreements between cities. The lines with * represent a commerce route starting in city 2 and ending in city 5.
This route never crosses itself. It would not be legal, for example, to construct a route that went from 2 to 6 to 5 to 1, since the route would cross itself.
* 1 * |* 2 * 7* | * / * * | / * * * |/ * 3 * /| * * * / | * * 6 ---+----------- 4 * | * 5
Cities in the lake are numbered from 1 through c moving in clockwise direction.
Write a program that, given both the count c of cities and a list of the commercial agreements between them, constructs a commerce route that meets the above requirements.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky