Task: Write a program which for given polygon constructs its arbitrary triangulation. Triangulation of a polygon is its partition into triangles, provided that these triangles do not overlap and their vertices are vertices of an original polygon. Polygon is given by the number of its vertices N and vertex coordinates listed counterclockwise. Output of the program is a list of constructed triangles.
Example:
Input:
N=5
[0,0],[2,2],[1,2],[2,3],[0,3]
Output:
([0,0],[2,2],[1,2])
([0,0],[1,2],[0,3])
([1,2],[2,3],[0,3])
Hedgehog's life is easy. When it huddles up, it needs only a very little space. On the other hand the life of a very long earthworm is quite difficult. It has segmented body which can bend only in "joints" between two segments. Fortunatelly, earthworms are very skillful. They can bend their joints backwards - so that the segments overlap.
Task: Write a program which for given lengths of earthworm's segments determines the minimal length of the folded earthworm. An earthworm is a line segment which can be bent in joints 0, or 180 degrees. Segments of an earthworm are given in the same order as they appear on earthworm.
Example:
Input:
Number of segments=5
Lengths of segments=1,3,2,3,2
Output:
Length of a folded earthworm is 4.
Diligent Tomas had his piano tuned up by the tuner who lives on the other end of the forest. It costed Tomas considerable amount of money. Moreover, now he must push the piano throught the forest back to his little burrow. The piano cannot be turned during the transport - centrifugal force caused by the rotation would lenghten the strings and the piano would be out of tune again.
Each of you has certainly pushed a piano through a forest and so you can imagine how difficult it is. It is advisable to check first whether it is possible to get the piano where you want to. On the northern side of the forest there is a river. There is no space between the northest tree of the forest and this river. Another river is on the southern side of the forest next to the southest three. Poor Tomas needs to know whether it is possible to push the piano from the eastern to the western side of the forest (without rotation).
Task: Write a program which for given number of trees and their coordinates and for given size of the (rectangular) piano determines whether it is possible to push the piano through the forest. At the beginning the piano is far away from the forest and its edges are parallel to the coordinate axes.
Note 1: The radius of trees is negligible.
Note 2: Neither the piano nor Tomas can swim.
Note for those who find this task easy: Consider the grand piano. It has the strings arranged in such way that it can be rotated without any harm.
Example:
Input:
The number of trees: 6
The trees' coordinates: [0,1],[3.5,3.5],[0.5,3],[2,0],[0,5],[2,1.5]
Size of the piano: x=3,y=2
Output:
The piano can be pushed through the forest.
Venetian~with~long~and~uncomprehensible~name is in a trouble. The local authorities has commissioned him to decide which of the town bridges are so important that their absence would paralyse the town traffic. A bridge is important if there are at least two significant sites which would be without connection in a case of the bridge's destruction. It is important to remember that in Venice there are no roads, only canals and bridges over them (and canals cannot be used for walking since your shoes get soaked quite quickly).
Task: Help Venetian~with~long~and~uncomprehensible~name and write a program which reads the number of significant sites N, the number of bridges M and M pairs of significant sites' numbers where the sites in each pair are directly connected with a bridge. The output of a program should be a list of all important bridges in Venice.
Example:
Input:
The number of significant sites: 7
The number of bridges: 8
Bridges: (1,2),(2,3),(4,7),(1,4),(3,6),(2,4),(5,6),(3,5)
Output:
Important Bridges: (2,3),(4,7)
Stevo and his friends went to the hiking trip. They went and went and finally they were so tired that they could not walk. They decided to make a break for lunch.
What did the students of the Faculty of Mathematics and Physics do during their lunch break in the forest? Each of them climbed to the crown of one tree and took out bread, bacon, onion and notebook from his or her backpack. When they got bored of eating alone and looking at their LCD displays, they connected their computers to the network. But they cannot use it because they do not know how to send e-mail to their friends.
Task: Each computer is connected with several other computers by individual links. The links of each computer are numbered from 1 to N, where N is the number of this computer's links. Each computer in the network has its unique name (string of at most 10 letters not containing spaces - e.g. FERDO). If computers A and B are connected by a link, the computer A can send the message to the computer B; the message is stored in B's mailbox.
Imagine this way of sending e-mails. The computer sends the e-mail to one of his links. The computer on the other end of the link receives the e-mail, finds out for whom it is and if it is not for this computer itself, sends it to one of his links ( re-routes it). In order to prevent the e-mails from wandering in the network for too long (or even for ever), each computer needs to know to which link to send the e-mail for any other computer in a network so that the e-mail gets to its receipient in the smallest possible number of re-routings. Each computer has this information stored in so called routing table.
Write a program which all Stevo's friends (Stevo is self-centered - he is his own friend) run on their notebooks (while eating their bacon) and after this program terminates, each of the computers will have its routing table. The program runs independently on each computer.
You can use following procedures for communication between computers (when using C language or other language, use procedures with similar structure; smes is the same as string, but its length is unconstrained):
Note: The computers should have their routing table ready before students eat all their bacon. Links are very slow and therefore try to minimaze their usage.