Runda 8 - Ogród pani Bajcyny

09.11.2009 - Marcin Oczeretko
TrudnośćTrudność

 

Zawody stałe, runda 8

Limit czasowy: 1s; Limit pamieciowy: 32 MB

 


Ogród Pani Bajcyny

 

Pani Bajcyna znana jest w okolicy ze swego zamiłowania do ogrodnictwa, jej wspaniały przydomowy ogródek wielokrotnie zdobywał laury w konkursach organizowanych przez Koło Wiejskich Programistek. Ostatnio wokół części upraw wzniesiono wysoki mur, a niektóre złośliwe sąsiadki twierdzą, że ma to pewien związek z nielegalnością uprawianych tam roślin! Pani Bajcyna uparcie zaprzecza jednak tym plotkom, zasłania się niepamięcią i odmawia udzielenia dalszych wyjaśnień. Postanowiła natomiast dodatkowo zabezpieczyć ogrodzenie i zainstalować w niektórych jego miejscach nowoczesne czujniki ruchu. Po kilku godzinach analizowania planu swej posesji, wymyśliła pewien sposób na ich rozmieszczenie. Chciała, aby czujniki były montowane w tych punktach ogrodzenia, które mają obie współrzędne całkowite. Niestety okazało się, że przekracza to możliwości finansowe pani Bajcyny. Firma monterska zaproponowała jej następujące rozwiązanie tego problemu: czujniki pojawią się tylko w tych punktach ogrodzenia, których obie współrzędne są liczbami pierwszymi. Zadziwiona pani Bajcyna próbowała zliczyć takie miejsca, ale zabrakło jej do tego cierpliwości. Pomóż pani Bajcynie!

Wejście


W pierwszej linii wejścia podana zostanie jedna liczba naturalna $ n $ $ \left(1\leq n \leq 100\right) $ oznaczająca ilość wierzchołków wielokąta, który symbolizuje na planie posesji nowopowstały mur. W kolejnych $ n $ wierszach pojawią się współrzędne kolejnych* wierzchołków tego wielokąta: będą to dwie liczby całkowite $ x_{i} $, $ y_{i} $ $ \left(0\leq x_{i}, y_{i} \leq 10^{5}\right) $. Możesz założyć, że boki mają wspólne punkty tylko w punktach połączeń między kolejnymi bokami. Wszystkie punkty na wejściu są różne.

* zgodnie z ruchem wskazówek zegara

Wyjście


Należy wypisać w ilu miejscach zamontowane zostaną czujniki ruchu.


Przykład 1:

Wejście:


5
1 1
1 6
4 6
5 5
5 1

Wyjście:


3

Punkty w których będą czujniki: (5,2), (5,3), (5,5)



Przykład 2:


Wejście:


9
1 1
3 3
1 12
14 14
11 8
14 7
11 1
7 5
5 1

Wyjście:


4

Punkty w których będą czujniki:

(2,2), (3,3), (13,5), (7,5)

 

Zapraszamy do dyskusji na temat zadania na forum.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Katarzyna Mandziuk1007:40:53
2Anna Piekarska10107:24:45
3Mateusz Wasilewski10350:01:39
4Janusz Wróbel10562:34:04
5Przemysław Derengowski101253:39:41
6Piotr Bryk101585:46:21
7Krzysztof Kapusta101596:19:02
8Michal Zgliczynski101710:55:21
9Maciej Kisiel107372:10:06
10Michał Karpiński107660:36:41
11Łukasz Hanuszczak109848:39:32
12Wojciech Kuprianowicz952:55:18
13Kamil Łukasz8293:41:30
14Marcin Pilecki8328:37:42
15Wojciech Kozaczewski463:16:36
16Darek Bukowski4154:48:56
17My My4209:21:03
18Kuba Skudlarski4398:49:24
3.25
Twoja ocena: Brak Ocena: 3.3 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com