KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 15 May 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley