Dva pravca
U ravnini se nalaze točke, neke od kojih su crvene, a neke plave. Točke su godinama živjele u mirnom suživotu, dok plave točke nisu pomahnitale i počele ničim izazvane napadati crvene točke. Kako bi se zaštitile, crvene točke su odlučile postaviti dva paralelna pravca takva da se između njih ne nalazi nijedna plava točka. Time bi bile zaštićene one crvene točke koje su smještene između tih pravaca. Pravci ne smiju prolaziti ni kroz plave ni kroz crvene točke. Crvene točke su primijetile da se ne mogu nužno sve zaštititi s dva pravca. Odredite koliko je najviše crvenih točaka moguće zaštititi.
InputU prvom redu nalazi se prirodni broj N (1 ≤ N ≤ 1000), broj točaka u ravnini. Svaki od sljedećih N redaka sadrži koordinate jedne točke i njezinu boju. Koordinate su par cijelih brojeva manjih od 109(milijardu) po apsolutnoj vrijednosti, a boja slovo 'C' ili 'P'. Ulazni podaci će biti takvi da neće postojati tri točke na istom pravcu.
OutputIspišite najveći broj crvenih točaka koji je moguće zaštititi s dva paralelna pravca.
Ulaz
Izlaz
4
0 0 C
0 1 P
1 1 C
1 0 P Izlaz
2Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.