Logo
(追記) (追記ここまで)

3878번 - 점 분리 다국어

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

문제

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

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

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

입력

첫째 줄에는 테스트 케이스의 개수 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

힌트

W3sicHJvYmxlbV9pZCI6IjM4NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHViZDg0XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzYzlcdWJhNzQgXHVjNzA0XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVhYzgwXHVjODE1IFx1YzgxMFx1YWNmYyBcdWQ3NzAgXHVjODEwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YzljMVx1YzEyMFx1Yzc0NCBcdWFkZjhcdWM1YjQgXHVkNzcwIFx1YzgxMFx1YWNmYyBcdWFjODBcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzljMVx1YzEyMFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjODEwXHVhY2ZjXHViM2M0IFx1YjljY1x1YjA5OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzc4XHVkNTc0XHVjMTFjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljMFx1YjI5NCBcdWI0NTAgXHVhZGY4XHViOGY5IFx1YzkxMSBcdWQ1NWMgXHVhZGY4XHViOGY5XHVjNWQwXHViMjk0IFx1ZDc3MCBcdWM4MTBcdWI5Y2MgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViMmU0XHViOTc4IFx1YWRmOFx1YjhmOVx1YzVkMFx1YjI5NCBcdWFjODBcdWM3NDAgXHVjODEwXHViOWNjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNzdjIFx1YzY3Y1x1Y2FiZCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjODEwXHVjMTIwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViNDUwIFx1YzgxMFx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YzgxMFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZXAucG5nXCIgc3R5bGU9XCJ3aWR0aDogNjE2cHg7IGhlaWdodDogMTc1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDc3MCBcdWM4MTBcdWFjZmMgXHVhYzgwXHVjNzQwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YzgxMFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM4MFx1YzgxNSBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWFjZmMgXHVkNzcwIFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1YWNmYyBtXHVjNzQwIDEwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM4MFx1YzgxNSBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDc3MCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzgxMFx1Yzc1OCB4LCB5XHVjODhjXHVkNDVjXHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM4MTBcdWM3NzQgMlx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM4MTBcdWM3NDQgXHViYjM4XHVjODFjXHVjNzU4IFx1YzEyNFx1YmE4NVx1YjMwMFx1Yjg1YyBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBZRVNcdWI5N2MsIFx1YzU0NFx1YjJjOFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzg3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlcGFyYXRlIFBvaW50cyIsImRlc2NyaXB0aW9uIjoiPHA+TnVtYmVycyBvZiBibGFjayBhbmQgd2hpdGUgcG9pbnRzIGFyZSBwbGFjZWQgb24gYSBwbGFuZS4gTGV0JnJzcXVvO3MgaW1hZ2luZSB0aGF0IGEgc3RyYWlnaHQgbGluZSBvZiBpblx1ZmIwMW5pdGUgbGVuZ3RoIGlzIGRyYXduIG9uIHRoZSBwbGFuZS4gV2hlbiB0aGUgbGluZSBkb2VzIG5vdCBtZWV0IGFueSBvZiB0aGUgcG9pbnRzLCB0aGUgbGluZSBkaXZpZGVzIHRoZXNlIHBvaW50cyBpbnRvIHR3byBncm91cHMuIElmIHRoZSBkaXZpc2lvbiBieSBzdWNoIGEgbGluZSByZXN1bHRzIGluIG9uZSBncm91cCBjb25zaXN0aW5nIG9ubHkgb2YgYmxhY2sgcG9pbnRzIGFuZCB0aGUgb3RoZXIgY29uc2lzdGluZyBvbmx5IG9mIHdoaXRlIHBvaW50cywgd2Ugc2F5IHRoYXQgdGhlIGxpbmUgJmxkcXVvO3NlcGFyYXRlcyBibGFjayBhbmQgd2hpdGUgcG9pbnRzJnJkcXVvOy48XC9wPlxyXG5cclxuPHA+TGV0JnJzcXVvO3Mgc2VlIGV4YW1wbGVzIGluIEZpZ3VyZSAzLiBJbiB0aGUgbGVmdG1vc3QgZXhhbXBsZSwgeW91IGNhbiBlYXNpbHkgZmluZCB0aGF0IHRoZSBibGFjayBhbmQgd2hpdGUgcG9pbnRzIGNhbiBiZSBwZXJmZWN0bHkgc2VwYXJhdGVkIGJ5IHRoZSBkYXNoZWQgbGluZSBhY2NvcmRpbmcgdG8gdGhlaXIgY29sb3JzLiBJbiB0aGUgcmVtYWluaW5nIHRocmVlIGV4YW1wbGVzLCB0aGVyZSBleGlzdHMgbm8gc3VjaCBzdHJhaWdodCBsaW5lIHRoYXQgZ2l2ZXMgc3VjaCBhIHNlcGFyYXRpb24uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2VwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3NXB4OyB3aWR0aDo2MTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMzogRXhhbXBsZSBwbGFuZXM8XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCBnaXZlbiBhIHNldCBvZiBwb2ludHMgd2l0aCB0aGVpciBjb2xvcnMgYW5kIHBvc2l0aW9ucywgeW91IGFyZSByZXF1ZXN0ZWQgdG8gZGVjaWRlIHdoZXRoZXIgdGhlcmUgZXhpc3RzIGEgc3RyYWlnaHQgbGluZSB0aGF0IHNlcGFyYXRlcyBibGFjayBhbmQgd2hpdGUgcG9pbnRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgZGF0YXNldHMsIGVhY2ggb2Ygd2hpY2ggaXMgZm9ybWF0dGVkIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm4gbVxyXG54PHN1Yj4xPFwvc3ViPiB5PHN1Yj4xPFwvc3ViPlxyXG4uLi5cclxueDxzdWI+bjxcL3N1Yj4geTxzdWI+bjxcL3N1Yj5cclxueDxzdWI+bisxPFwvc3ViPiB5PHN1Yj5uKzE8XC9zdWI+XHJcbi4uLlxyXG54PHN1Yj5uK208XC9zdWI+IHk8c3ViPm4rbTxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlOyBuIGlzIHRoZSBudW1iZXIgb2YgYmxhY2sgcG9pbnRzLCBhbmQgbSBpcyB0aGUgbnVtYmVyIG9mIHdoaXRlIHBvaW50cy4gVGhleSBhcmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEwMC4gVGhlbiBuICsgbSBsaW5lcyByZXByZXNlbnRpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHBvaW50cyBmb2xsb3cuIEVhY2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgeDxzdWI+aTxcL3N1Yj4gYW5kIHk8c3ViPmk8XC9zdWI+IHNlcGFyYXRlZCBieSBhIHNwYWNlLCB3aGVyZSAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KSByZXByZXNlbnRzIHRoZSB4LWNvb3JkaW5hdGUgYW5kIHRoZSB5LWNvb3JkaW5hdGUgb2YgdGhlIGktdGggcG9pbnQuIFRoZSBjb2xvciBvZiB0aGUgaS10aCBwb2ludCBpcyBibGFjayBmb3IgMSAmbGU7IGkgJmxlOyBuLCBhbmQgaXMgd2hpdGUgZm9yIG4gKyAxICZsZTsgaSAmbGU7IG4gKyBtLjxcL3A+XHJcblxyXG48cD5BbGwgdGhlIHBvaW50cyBoYXZlIGludGVncmFsIHgtIGFuZCB5LWNvb3JkaW5hdGUgdmFsdWVzIGJldHdlZW4gMCBhbmQgMTAwMDAgaW5jbHVzaXZlLiBZb3UgY2FuIGFsc28gYXNzdW1lIHRoYXQgbm8gdHdvIHBvaW50cyBoYXZlIHRoZSBzYW1lIHBvc2l0aW9uLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG91dHB1dCAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGVyZSBleGlzdHMgYSBsaW5lIHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbi4gSWYgbm90LCBvdXRwdXQgJmxkcXVvO05PJnJkcXVvOy4gSW4gZWl0aGVyIGNhc2UsIHByaW50IGl0IGluIG9uZSBsaW5lIGZvciBlYWNoIGlucHV0IGRhdGFzZXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /