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

문제

창영이는 새로 구입한 감시 카메라 세 개를 이용해서 소 N 마리(1 ≤ N ≤ 50,000)를 감시하려고 한다.

i번째 소의 위치는 (xi, yi)이다. xi와 yi는 0보다 크거나 같고, 1,000,000,000보다 작거나 같은 정수이다. 두 소가 같은 좌표를 가지는 경우는 없다. 

상근이의 감시 카메라는 한 수직선 또는 수평선 위에 있는 모든 소를 감시할 수 있다.

감시 카메라 세 개를 이용해서 모든 소를 감시할 수 있는지 없는지 구하는 프로그램을 작성하시오.

즉, 점 N개를 선분 3개를 이용해서 덮을 수 있는지 구하는 문제이다.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N개 줄에는 소의 좌표가 주어진다.

출력

모든 소를 감시 카메라로 감시할 수 있으면 1을 아니면 0을 출력한다. 

예제 입력 1

6
1 7
0 0
1 2
2 0
1 4
3 4

예제 출력 1

1

힌트

총 소가 6마리 있고, 소의 위치는 (1,7), (0,0), (1,2), (2,0), (1,4), (3,4) 이다. 감시 카메라를 y=0, x=1, y=4 로 설치하면 모든 소를 감시할 수 있다.

W3sicHJvYmxlbV9pZCI6IjU4ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1YyBcdWFkNmNcdWM3ODVcdWQ1NWMgXHVhYzEwXHVjMmRjIFx1Y2U3NFx1YmE1NFx1Yjc3YyBcdWMxMzggXHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMxOGMgTiBcdWI5YzhcdWI5YWMoMSAmbGU7IE4gJmxlOyA1MCwwMDApXHViOTdjIFx1YWMxMFx1YzJkY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHVjMThjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KVx1Yzc3NFx1YjJlNC4geDxzdWI+aTxcL3N1Yj5cdWM2NDAgeTxzdWI+aTxcL3N1Yj5cdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWI0NTAgXHVjMThjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjXHViMjk0IFx1ZDU1YyBcdWMyMThcdWM5YzFcdWMxMjAgXHViNjEwXHViMjk0IFx1YzIxOFx1ZDNjOVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMxOGNcdWI5N2MgXHVhYzEwXHVjMmRjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxMFx1YzJkYyBcdWNlNzRcdWJhNTRcdWI3N2MgXHVjMTM4IFx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViYWE4XHViNGUwIFx1YzE4Y1x1Yjk3YyBcdWFjMTBcdWMyZGNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjODEwIE5cdWFjMWNcdWI5N2MgXHVjMTIwXHViZDg0IDNcdWFjMWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjM2ZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMThjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwIFx1YzE4Y1x1Yjk3YyBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjXHViODVjIFx1YWMxMFx1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IDFcdWM3NDQgXHVjNTQ0XHViMmM4XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNkMWQgXHVjMThjXHVhYzAwIDZcdWI5YzhcdWI5YWMgXHVjNzg4XHVhY2UwLCBcdWMxOGNcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0ICgxLDcpLCAoMCwwKSwgKDEsMiksICgyLDApLCAoMSw0KSwgKDMsNCkgXHVjNzc0XHViMmU0LiBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjXHViOTdjIHk9MCwgeD0xLCB5PTQgXHViODVjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YmE3NCBcdWJhYThcdWI0ZTAgXHVjMThjXHViOTdjIFx1YWMxMFx1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTg4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRocmVlIExpbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiB3YW50cyB0byBtb25pdG9yIGhpcyBOIGNvd3MgKDEgJmx0Oz0gTiAmbHQ7PSA1MCwwMDApIHVzaW5nIGEgbmV3IHN1cnZlaWxsYW5jZSBzeXN0ZW0gaGUgaGFzIHB1cmNoYXNlZC4gJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpdGggY293IGlzIGxvY2F0ZWQgYXQgcG9zaXRpb24gKHhfaSwgeV9pKSB3aXRoIGludGVnZXIgY29vcmRpbmF0ZXMgKGluIHRoZSByYW5nZSAwLi4uMSwwMDAsMDAwLDAwMCk7IG5vIHR3byBjb3dzIG9jY3VweSB0aGUgc2FtZSBwb3NpdGlvbi4gJm5ic3A7RkomIzM5O3Mgc3VydmVpbGxhbmNlIHN5c3RlbSBjb250YWlucyB0aHJlZSBzcGVjaWFsIGNhbWVyYXMsIGVhY2ggb2Ygd2hpY2ggaXMgY2FwYWJsZSBvZiBvYnNlcnZpbmcgYWxsIHRoZSBjb3dzIGFsb25nIGVpdGhlciBhIHZlcnRpY2FsIG9yIGhvcml6b250YWwgbGluZS4gJm5ic3A7UGxlYXNlIGRldGVybWluZSBpZiBpdCBpcyBwb3NzaWJsZSBmb3IgRkogdG8gc2V0IHVwIHRoZXNlIHRocmVlIGNhbWVyYXMgc28gdGhhdCBoZSBjYW4gbW9uaXRvciBhbGwgTiBjb3dzLiAmbmJzcDtUaGF0IGlzLCBwbGVhc2UgZGV0ZXJtaW5lIGlmIHRoZSBOIGxvY2F0aW9ucyBvZiB0aGUgY293cyBjYW4gYWxsIGJlIHNpbXVsdGFuZW91c2x5ICZxdW90O2NvdmVyZWQmcXVvdDsgYnkgc29tZSBzZXQgb2YgdGhyZWUgbGluZXMsIGVhY2ggb2Ygd2hpY2ggaXMgb3JpZW50ZWQgZWl0aGVyIGhvcml6b250YWxseSBvciB2ZXJ0aWNhbGx5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBpbnRlZ2VyIE4uPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uMStOOiBMaW5lIGkrMSBjb250YWlucyB0aGUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXIgeF9pIGFuZCB5X2kgZ2l2aW5nIHRoZSBsb2NhdGlvbiBvZiBjb3cgaS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogUGxlYXNlIG91dHB1dCAxIGlmIGl0IGlzIHBvc3NpYmxlIHRvIG1vbml0b3IgYWxsIE4gY293cyB3aXRoIHRocmVlIGNhbWVyYXMsIG9yIDAgaWYgbm90LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlcmUgYXJlIDYgY293cywgYXQgcG9zaXRpb25zICgxLDcpLCAoMCwwKSwgKDEsMiksICgyLDApLCAoMSw0KSwgYW5kICgzLDQpLjxcL3A+XHJcblxyXG48cD5UaGUgbGluZXMgeT0wLCB4PTEsIGFuZCB5PTQgYXJlIGVhY2ggZWl0aGVyIGhvcml6b250YWwgb3IgdmVydGljYWwsIGFuZCBjb2xsZWN0aXZlbHkgdGhleSBjb250YWluIGFsbCBOIG9mIHRoZSBjb3cgbG9jYXRpb25zLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO US Open 2012 Contest > Bronze 2번