Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 35. (April 2008)

S. 35. We are given n points (1\len\le100) in the plane, each with integer coordinates. We would like to select some of these points such that one can always connect an arbitrary non-selected point and a suitable selected point with a line segment that contains only these two points and no others from the original set. Your task is to give such a selection with the above property, having the minimal number of elements.

Coordinate pairs are given in consecutive lines of a text file, separated by a space. The name of the input and output files are given as first and second command line arguments to your program. The output file should contain a list of the selected points in a similar format.

In the example, ``Bemenet'' means ``Input'', and ``Kimenet'' means ``Output''.

The source code of your program (s35.pas, s35.cpp, ...) together with a short documentation (s35.txt, s35.pdf, ...) should be submitted, also containing a short description of your code and the name of the developer environment to use.

(10 pont)

Deadline expired on May 15, 2008.


Sorry, the solution is available only in Hungarian. Google translation

A megoldást adó program a következőt teszi:

1. A bemeneti állomány feldolgozása után megvizsgálja, hogy mely pontok közé húzható más pontot nem tartalmazó szakasz.

2. Megszámolja, hogy melyik pontból hány ilyen szakasz húzható, és átrendezi a pontokat csökkenő sorrendbe aszerint, hogy hány másik pont "érhető el" belőlük.

3. Ezután visszalépéses kereséssel megvizsgálja, hogy a pontok melyik részhalmaza lesz megfelelő: először az egyelemű, aztán a kételemű, stb. halmazokat veszi. A keresés mindig a legkisebb indexű, tehát legtöbb másik pontot elérő szakaszokkal indul, ezért aránylag kevés eset végignézésével talál megoldást.

Az algoritmus a következő Pascal programban (Delphi Console alkalmazás) található: s35mo.dpr.

A beküldött munkákat a következő forrásokkal teszteltük: teszt.zip , és az s35ell.dpr (szintén Delphi karakteres ablakban futó) programmal ellenőriztük.


Statistics:

3 students sent a solution.
10 points:Weisz Ágoston.
5 points:2 students.

Problems in Information Technology of KöMaL, April 2008