Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_07_09 - Punkty |
Marek i Darek mają rozegrać mecz w pewną arcyciekawą grę - grę w Punkty. Poniżej w skrócie przedstawione zostały jej zasady:
- Sędzia podaje na początku współrzędne n punktów oraz połączenia pomiędzy nimi. W skutek połączeń pomiędzy danymi punktami powstać mogą dowolne wielokąty. Zadaniem sędziego jest dobrać punkty w taki sposób, aby odcinki w żadnym miejscu nie przecinały się, a powstałe figury nie miały ze sobą wspólnej krawędzi lub wierzchołka.
- Po krótkiej chwili jaką zawodnicy mają, aby wyobrazić sobie układ na planszy, sędzia podaje kolejne współrzędne m punktów, które traktować można jako zapytania.
- Za każdy punkt leżący wewnątrz wielokąta wypukłego zawodnicy do wyniku dodają 100 punktów.
- Za każdy punkt leżący wewnątrz wielokąta wklęsłego zawodnicy do wyniku dodają 11 punktów.
- Za każdy punkt, który nie znajduje się w obrębie żadnej z wyżej wymienionych figur należy odjąć 2 punkty od wyniku.
- Wygrywa ten, kto szybciej poda prawidłową liczbę punktów.
Koledzy dżentelmeńsko umówili się, że nie będą korzystać z kartek i długopisów lecz przecież nikt nic nie mówił o laptopie i napisanym specjalnie w tym celu programie! Marek zamierza skrzętnie wykorzystać tę lukę w zasadach rozgrywki i właśnie poprosił Ciebie o napisanie programu, który znacznie ułatwi mu wygraną.
Wejście
W pierwszej linii wejścia znajdują się trzy liczby n, l oraz m (3 ≤ n ≤ 300, 3 ≤ l ≤ 400, 1 ≤ m ≤ 104) określające odpowiednio liczbę punktów, połączeń pomiędzy nimi oraz zapytań. W drugiej linii znajduje się n współrzędnych punktów, potencjalnie tworzących figury, w formacie x1 y1, x2 y2, ..., xn yn (-6000 ≤ x, y ≤ 6000). Następujące po współrzędnych l linii to opis połączeń pomiędzy punktami (zapis 1 2 oznacza, że punkt którego współrzędne stanowią x1 y1 połączony jest z punktem o współrzędnych x2 y2). W kolejnych m liniach znajdują się zapytania - na każde z nich składają się współrzędne x oraz y (-6000 ≤ x, y ≤ 6000) pojedynczego punktu.
Wyjście
Na wyjściu należy wypisać jedną liczbę stanowiącą wynik gry.
Przykład
Wejście:
13 13 7 5 4 10 4 10 10 5 10 16 10 16 7 20 6 13 2 22 2 22 11 14 9 11 6 14 6 11 12 12 13 1 2 1 4 4 3 3 2 3 5 5 6 6 10 6 7 7 8 8 9 9 10 6 5 9 8 16 3 20 8 17 6 12 9 17 9
Wyjście:
216
Dodane przez: | Maciej Boniecki |
Data dodania: | 2013-06-06 |
Limit czasu wykonania programu: | 0.100s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 GOSU |
Pochodzenie: | ALGOLIGA |