Balkáni Informatikai Olimpia 1999

Egy rendőrségi alkalmazottnak kötelessége felvállalni a nagyváros bűnözésének statisztikai feldolgozását. Feladata meghatározni, hogy a város konvex sokszög alakú részén hány bűneset történt.

Bemenet:

A bemeneti állomány (INPUT.TXT) első sora egy egész számot tartalmaz, amely a feladatban szereplő konvex sokszög oldalszáma (3<=N<=1000). A következő N sor mindegyikében két egész szám található egy szóközzel elválasztva, amelyek a sokszög csúcsainak koordinátái (-1000<= X, Y <=1000). A következő sor a bűnesetek számát tartalmazza (1<= M <= 10000). Az ezt követő M sor mindegyikében két egész számot tartalmaz egy szóközzel elválasztva. A koordinátapárok a bűnesetek helyét írják le (-1000<= X, Y <=1000).

Kimenet:

Programodnak a kimeneti állományba (OUTPUT.TXT) egyetlen sort tartalmaz, amelybe azt a számot kell írni, ahány bűneset a megadott területen belül történt.

Példa:
 

INPUT.TXT	OUTPUT.TXT
4 0 0 0 100 100 100 100 0 2 50 50 -30 50	1

Két város, Westmouth és Eastmouth a Highwater folyó nyugati és keleti partján van, illetőleg Westmouth délre esik Eastmouthtól. A folyó partvonalait törött vonalak alkotják, a kelet-nyugati egyenes pontosan egy pontban metszi a partvonalat. Hook kapitány a két város között hajózik. Szeretné minimalizálni az üzemanyagköltséget, ezért meg akarja találni a legrövidebb útvonalat Westmouth és Eastmouth között.

Bemenet:

A bemeneti állomány (INPUT.TXT) első sora két egész számot tartalmaz (2<= M, N <= 2000), amelyek a nyugati, illetve keleti partot alkotó törött vonal csúcspontjait adják meg. A következő M sor két egészet tartalmaz (0 <= X, Y <= 3600), amelyek a nyugati part sarokpontjainak koordinátái. Ezután N sorban a keleti part leírása következik ehhez hasonlóan. Az első koordinátapár Westmouth, az utolsó Eastmouth helyét adja meg.

Kimenet:

A kimeneti állomány (OUTPUT.TXT) minden sorába két egészet kell írni, azon pontok koodinátáit, ahol irányt kell változtatni Westmouth és Eastmouth között. (A városok koordinátáit is ki kell írni.)

Példa:
 

INPUT.TXT	OUTPUT.TXT
3 3 0 0 50 50 0 150 100 0 50 100 100 150	0 0 50 50 50 100 100 150

Összejövetelt rendeztek egy nagy teremben. Minden meghívott esetében tudjuk, hogy kiket ismer a többi meghívott közül. Meg akarjuk tudni, az emberek sorbaállíthatók-e oly módon, hogy az egymást mellett állól ismerősök legyenek.

Bemenet:

A bemeneti állomány (INPUT.TXT) első sora az emberek számát tartalmazza (1 <= N <= 50). A második sor az ismerettségek számát adja meg (0 <= M <= 1225). A következő M sor mindegyike két egész számot tartalmaz (1 <= I, J <= N), amely két, számmal azonosított személy ismeri egymást.

Kimenet:

A kimeneti állomány (OUTPUT.TXT) első sorába a YES vagy NO szót kell írni, attól függően, hogy megoldható-e a feladat. Ha a válasz YES, a következő sorban egy lehetséges sorbaállítást kell megadni, a számokat szóközökkel elválasztva.

Példa:
 

INPUT.TXT	OUTPUT.TXT
5 7 1 2 3 1 2 3 2 4 4 3 3 5 4 5	YES 1 2 4 5 3