Runda 2: Witraż
25.11.2009
Limit czasu: 2s, limit pamięci: 32MB Pan Wincenty jest bardzo zadowolony, że udało mu się rozwiązać problem z ogrodem. Wolny czas, którego nagle mu przybyło, może wykorzystać do realizacji swoich zainteresowań (których ma nadzwyczaj wiele). Na przykład - nasz bohater od dawna chciał sprawdzić się w trudnej sztuce projektowania witraży. Pan Wincenty usiadł do biurka z ołówkiem i linijką, przygotował arkusz brystolu i zaczął kreślić. Jego pierwszy witraż był dość prosty - składał się z N prostych linii poprowadzonych przez arkusz. Po zakończonej pracy domorosły witrażysta policzył, ile kawałków szkła będzie potrzebnych do zbudowania witraża (na ile kawałków jego proste podzieliły brystol). Z pewną dozą rozczarowania pan Wincenty stwierdził, że liczba kawałków którą uzyskał jest niższa niżby chciał. Może powinienem poprzesuwać linie w projekcie? - zastanawiał się wpatrzony w rysunek. Znając linie narysowane przez pana Wincentego oblicz maksymalną liczbę segmentów witraża, jaką można uzyskać dowolnie przesuwając podane proste. WejścieW pierwszym wierszu znajduje się jedna liczba naturalna N (1 <= N <= 200 000) - liczba linii w projekcie. Następnie następuje ich opis w N kolejnych wierszach. Kążdą linię opisują podane kolejno (oddzielone spacjami) cztery liczby całkowite X1, Y1, X2, Y2 (-10000000 <= X1, Y1, X2, Y2 <= 10000000) oznaczające prostą przechodzącą przez punkty (X1,Y1) oraz (X2,Y2) - punkt (X1,Y1) danej linii będzie różny od jej punktu (X2,Y2). WyjścieOpisana wyżej maksymalna liczba kawałków witraża. Przykład
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto. (7 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com