[acm-valogato] feladat

Sziasztok! Az első kérdésem az lenne, hogy pénteken a szünet befolyásolja a foglakozást is? És küldenék még egy feladatot is, a 2006-os CH24 EC-en volt anno (lehet, hogy többen ismeritek): Problem B: Building Pipe Systems In the country of Elbonia, the citizens are gettingtir ed of havingno sanitation system. Together, they have saved some money to build a new pipe system that will connect their houses to the communal sanitation system. But since this is a small country, where most of the people have small incomes, they really want to build the cheapest system possible. The largest cost in this whole endeavour will be the pipes that must be put in the ground, connecting all the houses. Therefore, they need your help in minimizingthe total length of these pipes. A pipe system will connect all the houses together. The houses may either be connected house to house, or they may be connected via arbitrarily positioned junction points. Since Elbonia consists entirely of mud, the cost of layingdo wn the pipes is uniform over all the land. In other words, the only thingt hat matters is that the total length of pipes is as small as possible. Input Each test case contains the layout of one town. The consists of a number N, denoting the number of houses. Followingthis number come N lines, each containtinga pair xi yi denotingthe position of one house. The values xi and yi are both floatingp oint numbers of single precision length. Output For each test case, you will need to produce an output that represents a fully-connected pipe system. The smaller the total length of this pipe system, the higher the value of your solution will be. The representation of this pipe system should consist of the followingelemen ts. On the first line, a number M, where N ≤ M < 10 · N, denoting the number of points on the pipe system. Followingthis come M lines, each containinga pair xi yi denotingthe position of one house or one junction. The first N lines should contain the house locations from the input in the same order, while the next M − N lines contain your choosen junction postitions. Followingthis, on a new line, the number K of pipes that your pipe system has. On the following K lines, you should print pairs aj bj of numbers, where 0 ≤ aj, bj <M) and aj = bj, specifyingthe points connected by the pipe. Furthermore, each pair aj bj may only occur once in the pipe system. The indexingo f the points is zero-based. Scoring Your base score for a test case will be calculated as follows. Let Val be the length of your solution, and Opt be the length of the best solution of any team, including the judges’ solution. Then the base score of your solution is given by 1002−Val/Opt. In other words, if your solution matches the best solution, the base score will be 100, and if your solution is twice as longas the best solution, the base score will be 1. Üdv. Robi