시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3001449245.320%

문제

면 옛날에 좌표평면위에 빨간점과 파란점이 살고 있었다. 빨간점과 파란점은 몇 년동안 화목하게 지내고 있었다. 그런데... 파란점이 빨간점을 공격하기 시작했다. 빨간점은 파란점으로부터 자신들을 지키기 위해 두 평행선을 긋기로 결정했다. 두 선 사이에는 파란점이 있으면 안되며, 그 안에 있는 빨간점은 보호받을 수 있다. 선은 점을 지날 수 없다.

빨간점은 모든 빨간점이 보호받을 수 없음을 알게되었다. 보호받을 수 있는 빨간점 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

다음 N개 줄에는 각 점의 좌표와 색상이 주어진다. 좌표는 절댓값이 109보다 작은 정수쌍이고 색상은 'R'또는 'B'이다.

세 점이 일직선상에 있는 경우는 없다.

출력

두 평행선으로 보호받을 수 있는 빨간점 개수의 최댓값을 출력한다.

예제 입력 1

4
0 0 R
0 1 B
1 1 R
1 0 B

예제 출력 1

2

예제 입력 2

8
2 -3 R
4 -1 R
-2 0 R
-3 1 B
-2 3 R
1 4 R
2 1 B
0 -3 B

예제 출력 2

3
W3sicHJvYmxlbV9pZCI6IjMxMjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNjhcdWFjMDRcdWM4MTAsIFx1ZDMwY1x1Yjc4MFx1YzgxMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViYTc0IFx1YzYxYlx1YjBhMFx1YzVkMCBcdWM4OGNcdWQ0NWNcdWQzYzlcdWJhNzRcdWM3MDRcdWM1ZDAgXHViZTY4XHVhYzA0XHVjODEwXHVhY2ZjIFx1ZDMwY1x1Yjc4MFx1YzgxMFx1Yzc3NCBcdWMwYjRcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWJlNjhcdWFjMDRcdWM4MTBcdWFjZmMgXHVkMzBjXHViNzgwXHVjODEwXHVjNzQwIFx1YmE4NyBcdWIxNDRcdWIzZDlcdWM1NDggXHVkNjU0XHViYWE5XHVkNTU4XHVhYzhjIFx1YzljMFx1YjBiNFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MC4uLiBcdWQzMGNcdWI3ODBcdWM4MTBcdWM3NzQgXHViZTY4XHVhYzA0XHVjODEwXHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1YmU2OFx1YWMwNFx1YzgxMFx1Yzc0MCBcdWQzMGNcdWI3ODBcdWM4MTBcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVjNzkwXHVjMmUwXHViNGU0XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViNDUwIFx1ZDNjOVx1ZDU4OVx1YzEyMFx1Yzc0NCBcdWFlMGJcdWFlMzBcdWI4NWMgXHVhY2IwXHVjODE1XHVkNTg4XHViMmU0LiBcdWI0NTAgXHVjMTIwIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWQzMGNcdWI3ODBcdWM4MTBcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxOFx1YmE3MCwgXHVhZGY4IFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViZTY4XHVhYzA0XHVjODEwXHVjNzQwIFx1YmNmNFx1ZDYzOFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMxMjBcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YzljMFx1YjBhMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJlNjhcdWFjMDRcdWM4MTBcdWM3NDAgXHViYWE4XHViNGUwIFx1YmU2OFx1YWMwNFx1YzgxMFx1Yzc3NCBcdWJjZjRcdWQ2MzhcdWJjMWJcdWM3NDQgXHVjMjE4IFx1YzVjNlx1Yzc0Y1x1Yzc0NCBcdWM1NGNcdWFjOGNcdWI0MThcdWM1YzhcdWIyZTQuIFx1YmNmNFx1ZDYzOFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmU2OFx1YWMwNFx1YzgxMCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVjMGM5XHVjMGMxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODhjXHVkNDVjXHViMjk0IFx1YzgwOFx1YjMxM1x1YWMxMlx1Yzc3NCAxMDxzdXA+OTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzgxNVx1YzIxOFx1YzMwZFx1Yzc3NFx1YWNlMCBcdWMwYzlcdWMwYzFcdWM3NDAgJiMzOTtSJiMzOTtcdWI2MTBcdWIyOTQgJiMzOTtCJiMzOTtcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWM4MTBcdWM3NzQgXHVjNzdjXHVjOWMxXHVjMTIwXHVjMGMxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjQ1MCBcdWQzYzlcdWQ1ODlcdWMxMjBcdWM3M2NcdWI4NWMgXHViY2Y0XHVkNjM4XHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViZTY4XHVhYzA0XHVjODEwIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxMjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEVkFQUkFWQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBwb2ludHMgaW4gdGhlIHBsYW5lLCBzb21lIHJlZCBzb21lIGJsdWUuIFRoZSBwb2ludHMgbGl2ZWQgaW4gaGFybW9ueSBmb3IgeWVhcnMsIHVudGlsIHRoZSBibHVlIHBvaW50cyB3ZW50IGJvbmtlcnMgYW5kIHN0YXJ0ZWQgYXR0YWNraW5nIHJlZCBwb2ludHMuIFRvIHByb3RlY3QgdGhlbXNlbHZlcywgdGhlIHJlZCBwb2ludHMgZGVjaWRlZCB0byBlcmVjdCB0d28gcGFyYWxsZWwgbGluZXMgc3VjaCB0aGF0IG5vIGJsdWUgcG9pbnRzIGFyZSBjb250YWluZWQgYmV0d2VlbiB0aGUgbGluZXMuIEFsbCByZWQgcG9pbnRzIGJldHdlZW4gdGhlIGxpbmVzIHdpbGwgYmUgcHJvdGVjdGVkIGJ5IHRoZW0uIExpbmVzIG1heSBub3QgcGFzcyB0aHJvdWdoIGFueSBwb2ludHMsIHJlZCBvciBibHVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgcmVkIHBvaW50cyBvYnNlcnZlZCB0aGF0LCB1bmZvcnR1bmF0ZWx5LCBub3QgYWxsIG9mIHRoZW0gY2FuIGJlIHNhdmVzIGluIHRoaXMgd2F5LiBEZXRlcm1pbmUgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHJlZCBwb2ludHMgdGhhdCBjYW4gYmUgc2F2ZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2YgcG9pbnRzIGluIHRoZSBwbGFuZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSBwb2ludCBhbmQgaXRzIGNvbG91ci4gQ29vcmRpbmF0ZXMgYXJlIHBhaXJzIG9mIGludGVnZXJzIGxlc3MgdGhhbiAxMDxzdXA+OTxcL3N1cD4gKG9uZSBiaWxsaW9uKSBpbiBhYnNvbHV0ZSB2YWx1ZTsgdGhlIGNvbG91ciBpcyAmIzM5O1ImIzM5OyBvciAmIzM5O0ImIzM5Oy4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuJm5ic3A7Tm8gdGhyZWUgcG9pbnRzIHdpbGwgYmUgY29sbGluZWFyLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcmVkIHBvaW50cyB0aGF0IGNhbiBiZSBwcm90ZWN0ZWQgYnkgdHdvIHBhcmFsbGVsIGxpbmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Final Exam #2 1번