문제
좌표평면에 $N$개의 점이 주어진다. $i$번째 점의 좌표는 $(x_i, y_i)$이다. 모든 점들은 위치가 서로 다르며, 한 직선 위에 세 점이 놓이게 되는 경우는 없다.
당신의 목표는 점들의 쌍들 중 일부를 빨간색, 또는 파란색 선분으로 연결하여 다음 조건들을 모두 만족하도록 하는 것이다.
빨간색 선분만을 고려할 때, 모든 점들은 연결되어있다. 즉, 아무 서로다른 두 점을 잡아도 해당 두 점을 양 끝 점으로 가지는 빨간색 선분으로 이루어진 경로가 존재한다. 파란색 선분만을 고려할 때에도 성립한다.
임의의 두 선분이 두 선분의 끝점을 제외한 곳에서 교점을 가지지 않는다.
선분의 색상과 상관없이, 선분은 최대 2ドルN-2$개까지 존재한다.
조건을 모두 만족하도록 선분을 그릴 수 있는지 판별하고, 만약 가능하다면 답을 출력하라.
출력
만약 조건을 모두 만족하도록 점들을 연결하는 것이 불가능하다면, 첫 줄에 -1
그렇지 않을 경우, 답을 출력한다. 첫 줄에는 답에 사용된 선분의 개수 $m$을 출력한다.
다음 $m$개의 줄 중 $i$번째 줄에는 두 정수 $a_i$와 $b_i,ドル 한 문자 $c_i$를 공백을 사이에 두고 출력한다. 이는 답에 사용된 $i$번째 선분이 $a_i$번째, $b_i$번째 점을 끝점으로 하는 선분임을 의미하며, $c_i$가 RB
제한
3ドル \le N \le 2,000円$
모든 1ドル \le i \le N$에 대하여 $|x_i|, |y_i| \le 1,000円,000円,000円$
모든 1ドル \le i<j \le N$에 대하여 $(x_i, y_i) \ne (x_j, y_j)$
주어진 $N$개의 점 중 세 점이 한 직선 위에 놓이게 되는 경우는 없다.
서브태스크 번호 배점 제한 1 11 $N \le 5$
2 31 $N \le 100$
3 58 추가적인 제약 조건이 없다.
예제 출력 1
복사
6
1 3 R
1 4 R
1 2 B
4 3 B
2 3 B
2 4 R
예제 출력 2
복사
8
1 5 R
1 3 R
1 4 B
3 5 B
4 5 B
4 3 R
1 2 R
2 5 B
W3sicHJvYmxlbV9pZCI6IjMzODA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUmVkIGFuZCBCbHVlIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4OGNcdWQ0NWNcdWQzYzlcdWJhNzRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICRpJFx1YmM4OFx1YzlmOCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0ICQoeF9pLCB5X2kpJFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzgxMFx1YjRlNFx1Yzc0MCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YmE3MCwgXHVkNTVjIFx1YzljMVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjMTM4IFx1YzgxMFx1Yzc3NCBcdWIxOTNcdWM3NzRcdWFjOGMgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVjODEwXHViNGU0XHVjNzU4IFx1YzMwZFx1YjRlNCBcdWM5MTEgXHVjNzdjXHViZDgwXHViOTdjIFx1YmU2OFx1YWMwNFx1YzBjOSwgXHViNjEwXHViMjk0IFx1ZDMwY1x1Yjc4MFx1YzBjOSBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHVjNWVjIFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YmU2OFx1YWMwNFx1YzBjOSBcdWMxMjBcdWJkODRcdWI5Y2NcdWM3NDQgXHVhY2UwXHViODI0XHVkNTYwIFx1YjU0YywgXHViYWE4XHViNGUwIFx1YzgxMFx1YjRlNFx1Yzc0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVjNTQ0XHViYjM0IFx1YzExY1x1Yjg1Y1x1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjODEwXHVjNzQ0IFx1YzdhMVx1YzU0NFx1YjNjNCBcdWQ1NzRcdWIyZjkgXHViNDUwIFx1YzgxMFx1Yzc0NCBcdWM1OTEgXHViMDVkIFx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHViZTY4XHVhYzA0XHVjMGM5IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gIFx1ZDMwY1x1Yjc4MFx1YzBjOSBcdWMxMjBcdWJkODRcdWI5Y2NcdWM3NDQgXHVhY2UwXHViODI0XHVkNTYwIFx1YjU0Y1x1YzVkMFx1YjNjNCBcdWMxMzFcdWI5YmRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWI0NTAgXHVjMTIwXHViZDg0XHVjNzc0IFx1YjQ1MCBcdWMxMjBcdWJkODRcdWM3NTggXHViMDVkXHVjODEwXHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWFjZjNcdWM1ZDBcdWMxMWMgXHVhZDUwXHVjODEwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWFjZmMgXHVjMGMxXHVhZDAwXHVjNWM2XHVjNzc0LCBcdWMxMjBcdWJkODRcdWM3NDAgXHVjZDVjXHViMzAwICQyTi0yJFx1YWMxY1x1YWU0Y1x1YzljMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjODcwXHVhYzc0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YWNlMCwgXHViOWNjXHVjNTdkIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4MTBcdWM3NTggXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTiRcdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggJHhfaSwgeV9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YzgxMFx1YjRlNFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVjY2FiIFx1YzkwNFx1YzVkMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+LTE8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjYmRcdWM2YjAsIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmY1XHVjNWQwIFx1YzBhY1x1YzZhOVx1YjQxYyBcdWMxMjBcdWJkODRcdWM3NTggXHVhYzFjXHVjMjE4ICRtJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkbSRcdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggJGFfaSRcdWM2NDAgJGJfaSQsIFx1ZDU1YyBcdWJiMzhcdWM3OTAgJGNfaSRcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWIyOTQgXHViMmY1XHVjNWQwIFx1YzBhY1x1YzZhOVx1YjQxYyAkaSRcdWJjODhcdWM5ZjggXHVjMTIwXHViZDg0XHVjNzc0ICRhX2kkXHViYzg4XHVjOWY4LCAkYl9pJFx1YmM4OFx1YzlmOCBcdWM4MTBcdWM3NDQgXHViMDVkXHVjODEwXHVjNzNjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCAkY19pJFx1YWMwMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UjxcL2NvZGU+PFwvc3Bhbj5cdWM3N2MgXHVhY2JkXHVjNmIwIFx1YmU2OFx1YWMwNFx1YzBjOSwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkI8XC9jb2RlPjxcL3NwYW4+XHVjNzdjIFx1YWNiZFx1YzZiMCBcdWQzMGNcdWI3ODBcdWMwYzlcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMyBcXGxlIE4gXFxsZSAyXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgJDEgXFxsZSBpIFxcbGUgTiRcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjICR8eF9pfCwgfHlfaXwgXFxsZSAxXFwsMDAwXFwsMDAwXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgJDEgXFxsZSBpJmx0O2ogXFxsZSBOJFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgJCh4X2ksIHlfaSkgXFxuZSAoeF9qLCB5X2opJDxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzQgJE4kXHVhYzFjXHVjNzU4IFx1YzgxMCBcdWM5MTEgXHVjMTM4IFx1YzgxMFx1Yzc3NCBcdWQ1NWMgXHVjOWMxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM3NzRcdWFjOGMgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgNSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROIFxcbGUgMTAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzU1N2IzNDgyLTZlYzctNDkxOS04MTg1LTUyNWE2ODdlZTg5ZlwvLVwvcHJldmlld1wvXCIgXC8+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzM4MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWQgYW5kIEJsdWUiLCJkZXNjcmlwdGlvbiI6IjxwPiROJCBwb2ludHMgYXJlIGdpdmVuIG9uIHRoZSBDYXJ0ZXNpYW4gcGxhbmUuIFRoZSAkaSQtdGggcG9pbnQgaGFzIGNvb3JkaW5hdGVzICQoeF9pLCB5X2kpJC4gQWxsIHBvaW50cyBhcmUgcGFpcndpc2UgZGlzdGluY3QsIGFuZCBubyB0aHJlZSBwb2ludHMgbGllIG9uIGEgc3RyYWlnaHQgbGluZS48XC9wPlxyXG5cclxuPHA+WW91IG11c3QgY29ubmVjdCBzb21lIHBhaXJzIG9mIHBvaW50cyB3aXRoIGVpdGhlciByZWQgb3IgYmx1ZSBsaW5lIHNlZ21lbnRzIHNvIHRoYXQgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zIGFyZSBzYXRpc2ZpZWQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q29uc2lkZXJpbmcgb25seSB0aGUgcmVkIGxpbmUgc2VnbWVudHMsIGFsbCB0aGUgcG9pbnRzIG11c3QgYmUgY29ubmVjdGVkLiZuYnNwO1RoYXQgaXMsIGZvciBhbnkgdHdvIGRpc3RpbmN0IHBvaW50cywgdGhlcmUgZXhpc3RzIGEgcGF0aCBtYWRlIHVwIG9mIHJlZCBsaW5lIHNlZ21lbnRzIHRoYXQgaGFzIHRob3NlIHR3byBwb2ludHMgYXMgaXRzIGVuZHBvaW50cy4gVGhlIHNhbWUgbXVzdCBob2xkIGZvciB0aGUgYmx1ZSBsaW5lIHNlZ21lbnRzLjxcL2xpPlxyXG5cdDxsaT5BbnkgdHdvIGxpbmUgc2VnbWVudHMgbXVzdCBub3QgaW50ZXJzZWN0LCBleGNlcHQgcG9zc2libHkgYXQgdGhlaXIgZW5kcG9pbnRzLjxcL2xpPlxyXG5cdDxsaT5UaGUgdG90YWwgbnVtYmVyIG9mIGxpbmUgc2VnbWVudHMgKHJlZ2FyZGxlc3Mgb2YgdGhlaXIgY29sb3IpIG11c3QgYmUgYXQgbW9zdCAkMk4gLSAyJC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5EZXRlcm1pbmUgd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBkcmF3IHN1Y2ggc2VnbWVudHMgdG8gc2F0aXNmeSBhbGwgdGhlIGFib3ZlIGNvbmRpdGlvbnMuIElmIGl0IGlzIHBvc3NpYmxlLCBvdXRwdXQgYW55IHZhbGlkIGNvbmZpZ3VyYXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJCwmbmJzcDt0aGUgbnVtYmVyIG9mIHBvaW50cy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCAkTiQgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzICR4X2kkIGFuZCAkeV9pJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgaXQgaXMgaW1wb3NzaWJsZSB0byBjb25uZWN0IHRoZSBwb2ludHMgdG8gc2F0aXNmeSBhbGwgY29uZGl0aW9ucywgcHJpbnQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPi0xPFwvY29kZT48XC9zcGFuPiZuYnNwO2luIHRoZSBmaXJzdCBsaW5lLjxcL3A+XHJcblxyXG48cD5PdGhlcndpc2UsIHRoZSBmaXJzdCBsaW5lIHNob3VsZCBjb250YWluIGFuIGludGVnZXIgJG0kLCZuYnNwO3RoZSBudW1iZXIgb2YgbGluZSBzZWdtZW50cyB1c2VkLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICRtJCBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgJGFfaSQgYW5kICRiX2kkLCBhbmQgYSBjaGFyYWN0ZXIgJGNfaSQsIHNlcGFyYXRlZCBieSBzcGFjZXMuIEhlcmUsICRhX2kkIGFuZCAkYl9pJCBhcmUgdGhlIGVuZHBvaW50cyBvZiB0aGUgJGkkLXRoIHNlZ21lbnQsIGFuZCAkY19pJCBkZW5vdGVzIGl0cyBjb2xvci4gSWYgdGhlICRpJC10aCBzZWdtZW50IGlzIHJlZCwgdGhlbiAkY19pJCB3b3VsZCBiZSA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UjxcL2NvZGU+PFwvc3Bhbj47IGlmIGl0IGlzIGJsdWUsIHRoZW4gJGNfaSAkIHdvdWxkIGJlIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5CPFwvY29kZT48XC9zcGFuPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQzIFxcbGUgTiBcXGxlIDJcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiR8eF9pfCwgfHlfaXwgXFxsZSAxXFwsMDAwXFwsMDAwXFwsMDAwJCBmb3IgYWxsICQxIFxcbGUgaSBcXGxlIE4kPFwvbGk+XHJcblx0PGxpPiQoeF9pLCB5X2kpIFxcbmUgKHhfaiwgeV9qKSQgZm9yIGFsbCAkMSBcXGxlIGkmbHQ7aiBcXGxlIE4kPFwvbGk+XHJcblx0PGxpPlRoZXJlIGFyZSZuYnNwO25vIHRocmVlIHBvaW50cyB3aGljaCBmb3JtcyBhIHN0cmFpZ2h0IGxpbmUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgNSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROIFxcbGUgMTAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8zMTUxMjJjZC1kZjYyLTQ0MzYtOWRjYi01ZGZjMjYyZGMyZWFcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcbiJ9XQ==