시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 156 53 30 38.961%

문제

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

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

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

입력

첫째 줄에는 테스트 케이스의 개수 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
W3sicHJvYmxlbV9pZCI6IjM4NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHViZDg0XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQzYzlcdWJhNzQgXHVjNzA0XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVhYzgwXHVjODE1IFx1YzgxMFx1YWNmYyBcdWQ3NzAgXHVjODEwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWM5YzFcdWMxMjBcdWM3NDQgXHVhZGY4XHVjNWI0IFx1ZDc3MCBcdWM4MTBcdWFjZmMgXHVhYzgwXHVjNzQwIFx1YzgxMFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5YzFcdWMxMjBcdWM3NDAgXHVjNWI0XHViNWE0IFx1YzgxMFx1YWNmY1x1YjNjNCBcdWI5Y2NcdWIwOThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzc4XHVkNTc0XHVjMTFjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljMFx1YjI5NCBcdWI0NTAgXHVhZGY4XHViOGY5IFx1YzkxMSBcdWQ1NWMgXHVhZGY4XHViOGY5XHVjNWQwXHViMjk0IFx1ZDc3MCBcdWM4MTBcdWI5Y2MgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViMmU0XHViOTc4IFx1YWRmOFx1YjhmOVx1YzVkMFx1YjI5NCBcdWFjODBcdWM3NDAgXHVjODEwXHViOWNjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNzdjIFx1YzY3Y1x1Y2FiZCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjODEwXHVjMTIwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViNDUwIFx1YzgxMFx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YzgxMFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZXAucG5nXCIgc3R5bGU9XCJ3aWR0aDogNjE2cHg7IGhlaWdodDogMTc1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDc3MCBcdWM4MTBcdWFjZmMgXHVhYzgwXHVjNzQwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YzgxMFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzgwXHVjODE1IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWQ3NzAgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBtXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVhY2ZjIG1cdWM3NDAgMTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzgwXHVjODE1IFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzcwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHVjODEwXHVjNzU4IHgseVx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWFjMTJcdWM3NDAgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjODEwXHVjNzc0IDJcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjODEwXHVjNzQ0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWMxMjRcdWJhODVcdWIzMDBcdWI4NWMgXHViZDg0XHViOWFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgWUVTXHViOTdjLCBcdWM1NDRcdWIyYzhcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZXBhcmF0ZSBQb2ludHMiLCJkZXNjcmlwdGlvbiI6IjxwPk51bWJlcnMgb2YgYmxhY2sgYW5kIHdoaXRlIHBvaW50cyBhcmUgcGxhY2VkIG9uIGEgcGxhbmUuIExldCZyc3F1bztzIGltYWdpbmUgdGhhdCBhIHN0cmFpZ2h0IGxpbmUgb2YgaW5cdWZiMDFuaXRlIGxlbmd0aCBpcyBkcmF3biBvbiB0aGUgcGxhbmUuIFdoZW4gdGhlIGxpbmUgZG9lcyBub3QgbWVldCBhbnkgb2YgdGhlIHBvaW50cywgdGhlIGxpbmUgZGl2aWRlcyB0aGVzZSBwb2ludHMgaW50byB0d28gZ3JvdXBzLiBJZiB0aGUgZGl2aXNpb24gYnkgc3VjaCBhIGxpbmUgcmVzdWx0cyBpbiBvbmUgZ3JvdXAgY29uc2lzdGluZyBvbmx5IG9mIGJsYWNrIHBvaW50cyBhbmQgdGhlIG90aGVyIGNvbnNpc3Rpbmcgb25seSBvZiB3aGl0ZSBwb2ludHMsIHdlIHNheSB0aGF0IHRoZSBsaW5lICZsZHF1bztzZXBhcmF0ZXMgYmxhY2sgYW5kIHdoaXRlIHBvaW50cyZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkxldCZyc3F1bztzIHNlZSBleGFtcGxlcyBpbiBGaWd1cmUgMy4gSW4gdGhlIGxlZnRtb3N0IGV4YW1wbGUsIHlvdSBjYW4gZWFzaWx5IGZpbmQgdGhhdCB0aGUgYmxhY2sgYW5kIHdoaXRlIHBvaW50cyBjYW4gYmUgcGVyZmVjdGx5IHNlcGFyYXRlZCBieSB0aGUgZGFzaGVkIGxpbmUgYWNjb3JkaW5nIHRvIHRoZWlyIGNvbG9ycy4gSW4gdGhlIHJlbWFpbmluZyB0aHJlZSBleGFtcGxlcywgdGhlcmUgZXhpc3RzIG5vIHN1Y2ggc3RyYWlnaHQgbGluZSB0aGF0IGdpdmVzIHN1Y2ggYSBzZXBhcmF0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NlcC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzVweDsgd2lkdGg6NjE2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDM6IEV4YW1wbGUgcGxhbmVzPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgZ2l2ZW4gYSBzZXQgb2YgcG9pbnRzIHdpdGggdGhlaXIgY29sb3JzIGFuZCBwb3NpdGlvbnMsIHlvdSBhcmUgcmVxdWVzdGVkIHRvIGRlY2lkZSB3aGV0aGVyIHRoZXJlIGV4aXN0cyBhIHN0cmFpZ2h0IGxpbmUgdGhhdCBzZXBhcmF0ZXMgYmxhY2sgYW5kIHdoaXRlIHBvaW50cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGRhdGFzZXRzLCBlYWNoIG9mIHdoaWNoIGlzIGZvcm1hdHRlZCBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48cHJlPlxyXG5uIG1cclxueDxzdWI+MTxcL3N1Yj4geTxzdWI+MTxcL3N1Yj5cclxuLi4uXHJcbng8c3ViPm48XC9zdWI+IHk8c3ViPm48XC9zdWI+XHJcbng8c3ViPm4rMTxcL3N1Yj4geTxzdWI+bisxPFwvc3ViPlxyXG4uLi5cclxueDxzdWI+bittPFwvc3ViPiB5PHN1Yj5uK208XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZTsgbiBpcyB0aGUgbnVtYmVyIG9mIGJsYWNrIHBvaW50cywgYW5kIG0gaXMgdGhlIG51bWJlciBvZiB3aGl0ZSBwb2ludHMuIFRoZXkgYXJlIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMDAuIFRoZW4gbiArIG0gbGluZXMgcmVwcmVzZW50aW5nIHRoZSBjb29yZGluYXRlcyBvZiBwb2ludHMgZm9sbG93LiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIHg8c3ViPmk8XC9zdWI+IGFuZCB5PHN1Yj5pPFwvc3ViPiBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgd2hlcmUgKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPikgcmVwcmVzZW50cyB0aGUgeC1jb29yZGluYXRlIGFuZCB0aGUgeS1jb29yZGluYXRlIG9mIHRoZSBpLXRoIHBvaW50LiBUaGUgY29sb3Igb2YgdGhlIGktdGggcG9pbnQgaXMgYmxhY2sgZm9yIDEgJmxlOyBpICZsZTsgbiwgYW5kIGlzIHdoaXRlIGZvciBuICsgMSAmbGU7IGkgJmxlOyBuICsgbS48XC9wPlxyXG5cclxuPHA+QWxsIHRoZSBwb2ludHMgaGF2ZSBpbnRlZ3JhbCB4LSBhbmQgeS1jb29yZGluYXRlIHZhbHVlcyBiZXR3ZWVuIDAgYW5kIDEwMDAwIGluY2x1c2l2ZS4gWW91IGNhbiBhbHNvIGFzc3VtZSB0aGF0IG5vIHR3byBwb2ludHMgaGF2ZSB0aGUgc2FtZSBwb3NpdGlvbi48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgJmxkcXVvO1lFUyZyZHF1bzsgaWYgdGhlcmUgZXhpc3RzIGEgbGluZSBzYXRpc2Z5aW5nIHRoZSBjb25kaXRpb24uIElmIG5vdCwgb3V0cHV0ICZsZHF1bztOTyZyZHF1bzsuIEluIGVpdGhlciBjYXNlLCBwcmludCBpdCBpbiBvbmUgbGluZSBmb3IgZWFjaCBpbnB1dCBkYXRhc2V0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==