Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ETI06E3 - Wyścigi biedronek

Jaś zorganizował wyścigi biedronek na swojej szkolnej ławce. Dla uproszczenia, będzie przyjmować, że ławka jest płaska, a współrzędne punktów wyraża się poprzez ich współrzędne kartezjańskie (x,y). Każda z n biedronek została rozmieszczona w odpowiednim miejscu na linii startu, w punkcie o współrzędnych (xSi,0), i została poinformowana o punkcie końcowym swojej trasy, o współrzędnych (xFi,yFi), gdzie 1<=i<=n . Po rozpoczęciu wyścigu biedronki podążają zawsze po najkrótszej drodze bezpośrednio do swojego celu, lecz niekoniecznie ze stałą prędkością.

Powstał jednak pewien problem. Gdy Pani Wychowawczyni dowiedziała się o planowanym wyścigu, zdecydowanie zaprotestowała, twierdząc, że jest całkowicie niedopuszczalne, by trasy, wzdłuż których poruszają się biedronki, przecinały się, gdyż biedne owady mogą się ze sobą zderzyć.

Chcąc nie chcąc, Jaś musi przychylić się do żądania Pani. Ponieważ jest już za późno, by zmienić tory wyścigowe, niezbędne okazało się wycofanie części biedronek z wyścigu. Spróbuj określić, ile maksymalnie biedronek może pozostać w rozgrywkach.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą n, określającą początkową liczbę ustawionych do wyścigu biedronek (1<=n<=200). Każdy z kolejnych n wierszy zawiera po trzy liczby całkowite xSi xFi yFi oddzielone spacjami, opisujące punkty startowe i końcowe tras poszczególnych biedronek (-40000<=xSi,xFi<=40000, 0< yFi<=40000).

Wyjście

Należy wypisać pojedynczą liczbę całkowitą, równą maksymalnej liczbie biedronek, które mogą pozostać w wyścigu, przy założeniu, że żadne dwa z pozostawionych torów wyścigowych nie mogą mieć punktu wspólnego (włącznie z punktami startu i zakończenia trasy).

Przykłady

Zestaw przykładowy 1

Wejście:
3
0 0 10
-10 0 10
10 0 10 

Wyjście
1


Zestaw przykładowy 2

Wejście:
6
0 2 2
2 1 2
3 3 2
4 4 4
3 4 2
4 3 2

Wyjście
3

Dodane przez:adrian
Data dodania:2005-11-11
Limit czasu wykonania programu:0.119s-0.523s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2015-10-26 22:07:02
Czy problem jest NP ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.