시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 171 42 30 30.303%

문제

평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안된다. 직선으로 인해서 나누어지는 두 그룹 중 한 그룹에는 흰 점만 있어야 하고, 다른 그룹에는 검은 점만 있어야 한다.

아래 그림에서 제일 왼쪽 예제는 점선으로 표시된 직선으로 두 점을 나눌 수 있다. 하지만 나머지 예제는 직선으로 점을 분리할 수 없다.

흰 점과 검은 점의 좌표가 주어졌을 때, 직선으로 점을 분리할 수 있는지 없는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에 검정 점의 개수 n과 흰 점의 개수 m이 공백으로 구분되어 주어진다. n과 m은 100보다 작거나 같다. 다음 줄부터 n개의 줄에는 검정 점의 좌표가 공백으로 구분되어 주어진다. 그 다음 m개의 줄에는 흰 점의 좌표가 주어진다.

모든 점의 x,y좌표의 값은 0보다 크거나 같고, 10000보다 작거나 같다. 또한, 같은 위치에 점이 2개 이상 있는 경우는 없다.

출력

각각의 테스트 케이스에 대해서, 점을 문제의 설명대로 분리할 수 있으면 YES를, 아니면 NO를 출력한다.

예제 입력 1

10
3 3
100 700
200 200
600 600
500 100
500 300
800 500
3 3
100 300
400 600
400 100
600 400
500 900
300 300
3 4
300 300
500 300
400 600
100 100
200 900
500 900
800 100
1 2
300 300
100 100
500 500
1 1
100 100
200 100
2 2
0 0
500 700
1000 1400
1500 2100
2 2
0 0
1000 1000
1000 0
0 1000
3 3
0 100
4999 102
10000 103
5001 102
10000 102
0 101
3 3
100 100
200 100
100 200
0 0
400 0
0 400
3 3
2813 1640
2583 2892
2967 1916
541 3562
9298 3686
7443 7921

예제 출력 1

YES
NO
NO
NO
YES
YES
NO
NO
NO
YES
W3sicHJvYmxlbV9pZCI6IjM4NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHViZDg0XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQzYzlcdWJhNzQgXHVjNzA0XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVhYzgwXHVjODE1IFx1YzgxMFx1YWNmYyBcdWQ3NzAgXHVjODEwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YzljMVx1YzEyMFx1Yzc0NCBcdWFkZjhcdWM1YjQgXHVkNzcwIFx1YzgxMFx1YWNmYyBcdWFjODBcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzljMVx1YzEyMFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjODEwXHVhY2ZjXHViM2M0IFx1YjljY1x1YjA5OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzhcdWQ1NzRcdWMxMWMgXHViMDk4XHViMjA0XHVjNWI0XHVjOWMwXHViMjk0IFx1YjQ1MCBcdWFkZjhcdWI4ZjkgXHVjOTExIFx1ZDU1YyBcdWFkZjhcdWI4ZjlcdWM1ZDBcdWIyOTQgXHVkNzcwIFx1YzgxMFx1YjljYyBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVhZGY4XHViOGY5XHVjNWQwXHViMjk0IFx1YWM4MFx1Yzc0MCBcdWM4MTBcdWI5Y2MgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWM4MWNcdWM3N2MgXHVjNjdjXHVjYWJkIFx1YzYwOFx1YzgxY1x1YjI5NCBcdWM4MTBcdWMxMjBcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWI0NTAgXHVjODEwXHVjNzQ0IFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViMDk4XHViYTM4XHVjOWMwIFx1YzYwOFx1YzgxY1x1YjI5NCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODEwXHVjNzQ0IFx1YmQ4NFx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NlcC5wbmdcIiBzdHlsZT1cIndpZHRoOiA2MTZweDsgaGVpZ2h0OiAxNzVweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkNzcwIFx1YzgxMFx1YWNmYyBcdWFjODBcdWM3NDAgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODEwXHVjNzQ0IFx1YmQ4NFx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG5cclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjODBcdWM4MTUgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVhY2ZjIFx1ZDc3MCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWFjZmMgbVx1Yzc0MCAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjODBcdWM4MTUgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ3NzAgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWM4MTBcdWM3NTggeCx5XHVjODhjXHVkNDVjXHVjNzU4IFx1YWMxMlx1Yzc0MCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM4MTBcdWM3NzQgMlx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM4MTBcdWM3NDQgXHViYjM4XHVjODFjXHVjNzU4IFx1YzEyNFx1YmE4NVx1YjMwMFx1Yjg1YyBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBZRVNcdWI5N2MsIFx1YzU0NFx1YjJjOFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlcGFyYXRlIFBvaW50cyIsImRlc2NyaXB0aW9uIjoiPHA+TnVtYmVycyBvZiBibGFjayBhbmQgd2hpdGUgcG9pbnRzIGFyZSBwbGFjZWQgb24gYSBwbGFuZS4gTGV0JnJzcXVvO3MgaW1hZ2luZSB0aGF0IGEgc3RyYWlnaHQgbGluZSBvZiBpblx1ZmIwMW5pdGUgbGVuZ3RoIGlzIGRyYXduIG9uIHRoZSBwbGFuZS4gV2hlbiB0aGUgbGluZSBkb2VzIG5vdCBtZWV0IGFueSBvZiB0aGUgcG9pbnRzLCB0aGUgbGluZSBkaXZpZGVzIHRoZXNlIHBvaW50cyBpbnRvIHR3byBncm91cHMuIElmIHRoZSBkaXZpc2lvbiBieSBzdWNoIGEgbGluZSByZXN1bHRzIGluIG9uZSBncm91cCBjb25zaXN0aW5nIG9ubHkgb2YgYmxhY2sgcG9pbnRzIGFuZCB0aGUgb3RoZXIgY29uc2lzdGluZyBvbmx5IG9mIHdoaXRlIHBvaW50cywgd2Ugc2F5IHRoYXQgdGhlIGxpbmUgJmxkcXVvO3NlcGFyYXRlcyBibGFjayBhbmQgd2hpdGUgcG9pbnRzJnJkcXVvOy48XC9wPlxyXG5cclxuPHA+TGV0JnJzcXVvO3Mgc2VlIGV4YW1wbGVzIGluIEZpZ3VyZSAzLiBJbiB0aGUgbGVmdG1vc3QgZXhhbXBsZSwgeW91IGNhbiBlYXNpbHkgZmluZCB0aGF0IHRoZSBibGFjayBhbmQgd2hpdGUgcG9pbnRzIGNhbiBiZSBwZXJmZWN0bHkgc2VwYXJhdGVkIGJ5IHRoZSBkYXNoZWQgbGluZSBhY2NvcmRpbmcgdG8gdGhlaXIgY29sb3JzLiBJbiB0aGUgcmVtYWluaW5nIHRocmVlIGV4YW1wbGVzLCB0aGVyZSBleGlzdHMgbm8gc3VjaCBzdHJhaWdodCBsaW5lIHRoYXQgZ2l2ZXMgc3VjaCBhIHNlcGFyYXRpb24uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2VwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3NXB4OyB3aWR0aDo2MTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMzogRXhhbXBsZSBwbGFuZXM8XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCBnaXZlbiBhIHNldCBvZiBwb2ludHMgd2l0aCB0aGVpciBjb2xvcnMgYW5kIHBvc2l0aW9ucywgeW91IGFyZSByZXF1ZXN0ZWQgdG8gZGVjaWRlIHdoZXRoZXIgdGhlcmUgZXhpc3RzIGEgc3RyYWlnaHQgbGluZSB0aGF0IHNlcGFyYXRlcyBibGFjayBhbmQgd2hpdGUgcG9pbnRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgZGF0YXNldHMsIGVhY2ggb2Ygd2hpY2ggaXMgZm9ybWF0dGVkIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm4gbVxyXG54PHN1Yj4xPFwvc3ViPiB5PHN1Yj4xPFwvc3ViPlxyXG4uLi5cclxueDxzdWI+bjxcL3N1Yj4geTxzdWI+bjxcL3N1Yj5cclxueDxzdWI+bisxPFwvc3ViPiB5PHN1Yj5uKzE8XC9zdWI+XHJcbi4uLlxyXG54PHN1Yj5uK208XC9zdWI+IHk8c3ViPm4rbTxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlOyBuIGlzIHRoZSBudW1iZXIgb2YgYmxhY2sgcG9pbnRzLCBhbmQgbSBpcyB0aGUgbnVtYmVyIG9mIHdoaXRlIHBvaW50cy4gVGhleSBhcmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEwMC4gVGhlbiBuICsgbSBsaW5lcyByZXByZXNlbnRpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHBvaW50cyBmb2xsb3cuIEVhY2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgeDxzdWI+aTxcL3N1Yj4gYW5kIHk8c3ViPmk8XC9zdWI+IHNlcGFyYXRlZCBieSBhIHNwYWNlLCB3aGVyZSAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KSByZXByZXNlbnRzIHRoZSB4LWNvb3JkaW5hdGUgYW5kIHRoZSB5LWNvb3JkaW5hdGUgb2YgdGhlIGktdGggcG9pbnQuIFRoZSBjb2xvciBvZiB0aGUgaS10aCBwb2ludCBpcyBibGFjayBmb3IgMSAmbGU7IGkgJmxlOyBuLCBhbmQgaXMgd2hpdGUgZm9yIG4gKyAxICZsZTsgaSAmbGU7IG4gKyBtLjxcL3A+XHJcblxyXG48cD5BbGwgdGhlIHBvaW50cyBoYXZlIGludGVncmFsIHgtIGFuZCB5LWNvb3JkaW5hdGUgdmFsdWVzIGJldHdlZW4gMCBhbmQgMTAwMDAgaW5jbHVzaXZlLiBZb3UgY2FuIGFsc28gYXNzdW1lIHRoYXQgbm8gdHdvIHBvaW50cyBoYXZlIHRoZSBzYW1lIHBvc2l0aW9uLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG91dHB1dCAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGVyZSBleGlzdHMgYSBsaW5lIHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbi4gSWYgbm90LCBvdXRwdXQgJmxkcXVvO05PJnJkcXVvOy4gSW4gZWl0aGVyIGNhc2UsIHByaW50IGl0IGluIG9uZSBsaW5lIGZvciBlYWNoIGlucHV0IGRhdGFzZXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2009 in Tokyo D번