Runda 2: Witraż

25.11.2009
Trudność

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ście

W 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ście

Opisana wyżej maksymalna liczba kawałków witraża.

Przykład

WejścieWyjście

3
-1 -1 1 1
0 -1 0 1
-1 0 1 0

7

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.857145
Twoja ocena: Brak Ocena: 4.9 (7 ocen)

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com