KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 15 May 2008.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem S. 35.
3 students sent a solution.
10 points:Weisz Ágoston.
5 points:2 students.


  • Problems in Information Technology of KöMaL, April 2008

  • Támogatóink:   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