시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 48 19 13 50.000%

문제

상근이네 집 근처에는 군사 기지가 있다. 군사 기지에는 참호가 많이 있으며, 참호는 평면 위의 선분으로 모델링 할 수 있다.

매일 밤 대부분의 군인들은 잠을 자고, 군인 세 명은 밤새도록 참호를 감시한다. 두 군인이 서로 볼 수 있으려면, 그들 연결하는 선분이 모두 참호안에 있어야 하며, 다른 군인은 그 사이에 없어야 한다.

보안 상의 이유 때문에 군인은 모두 서로를 볼 수 있어야 한다. 군인을 배치할 수 있는 방법의 수는 총 몇 가지가 있을까?

입력

첫째 줄에 참호의 수 N이 주어진다. (1 ≤ N ≤ 20) 다음 N개 줄에는 참호의 정보가 네 양의 정수 X1, Y1, X2, Y2로 주어진다. 좌표는 모두 1000보다 작거나 같은 양의 정수 또는 0이다. (X1, Y1)과 (X2, Y2)는 참호의 양 끝 점이다.

참호는 겹칠 수도 있으며, 끝 점을 공유할 수도 있다.

출력

첫째 줄에 군인을 배치하는 방법의 수를 출력한다.

예제 입력 1

6
0 0 1 0
0 0 0 1
1 0 1 1
0 1 1 1
0 0 1 1
1 0 0 1

예제 출력 1

8

예제 입력 2

4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4

예제 출력 2

1

예제 입력 3

3
2 2 3 2
3 2 3 3
3 3 2 3

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjMwNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNzBcdWMwYWMgXHVhZTMwXHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjOWQxIFx1YWRmY1x1Y2M5OFx1YzVkMFx1YjI5NCBcdWFkNzBcdWMwYWMgXHVhZTMwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhZDcwXHVjMGFjIFx1YWUzMFx1YzljMFx1YzVkMFx1YjI5NCBcdWNjMzhcdWQ2MzhcdWFjMDAgXHViOWNlXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjYzM4XHVkNjM4XHViMjk0IFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM3NTggXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YmFhOFx1YjM3OFx1YjljMSBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0XHVjNzdjIFx1YmMyNCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVhZDcwXHVjNzc4XHViNGU0XHVjNzQwIFx1YzdhMFx1Yzc0NCBcdWM3OTBcdWFjZTAsIFx1YWQ3MFx1Yzc3OCBcdWMxMzggXHViYTg1XHVjNzQwIFx1YmMyNFx1YzBjOFx1YjNjNFx1Yjg1ZCBcdWNjMzhcdWQ2MzhcdWI5N2MgXHVhYzEwXHVjMmRjXHVkNTVjXHViMmU0LiBcdWI0NTAgXHVhZDcwXHVjNzc4XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YjgyNFx1YmE3NCwgXHVhZGY4XHViNGU0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NzQgXHViYWE4XHViNDUwIFx1Y2MzOFx1ZDYzOFx1YzU0OFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWIyZTRcdWI5NzggXHVhZDcwXHVjNzc4XHVjNzQwIFx1YWRmOCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNWM2XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2Y0XHVjNTQ4IFx1YzBjMVx1Yzc1OCBcdWM3NzRcdWM3MjAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWQ3MFx1Yzc3OFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMTFjXHViODVjXHViOTdjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZDcwXHVjNzc4XHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIFx1YmE4NyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMzhcdWQ2MzhcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2MzOFx1ZDYzOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHViMTI0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggWDEsIFkxLCBYMiwgWTJcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViYWE4XHViNDUwIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YjYxMFx1YjI5NCAwXHVjNzc0XHViMmU0LiAoWDEsIFkxKVx1YWNmYyAoWDIsIFkyKVx1YjI5NCBcdWNjMzhcdWQ2MzhcdWM3NTggXHVjNTkxIFx1YjA1ZCBcdWM4MTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzOFx1ZDYzOFx1YjI5NCBcdWFjYjlcdWNlNjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViMDVkIFx1YzgxMFx1Yzc0NCBcdWFjZjVcdWM3MjBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWQ3MFx1Yzc3OFx1Yzc0NCBcdWJjMzBcdWNlNThcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA1MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNUUkFcdTAxN2RBIiwiZGVzY3JpcHRpb24iOiI8cD5OZWFyIGEgbWlsaXRhcnkgYmFzZSB0aGVyZSBpcyBhIHN5c3RlbSBvZiB0cmVuY2hlcywgbW9kZWxlZCBhcyBsaW5lIHNlZ21lbnRzIG9uIGEgcGxhbmUuIER1cmluZyBuaWdodHRpbWUsIHdoZW4gbW9zdCBzb2xkaWVycyBhcmUgZmFzdCBhc2xlZXAsIHRocmVlIGd1YXJkcyBzdGFuZCB3YXRjaCBvZiB0aGUgdHJlbmNoZXMuIFR3byBndWFyZHMgY2FuIHNlZSBlYWNoIG90aGVyIGlmIHRoZXJlIGlzIGEgdHJlbmNoIChvciBhIHJvdyBvZiB0cmVuY2hlcykgYWxvbmcgdGhlIGVudGlyZSBzdHJhaWdodCBsaW5lIHNlZ21lbnQgYmV0d2VlbiB0aGVtIGFuZCB0aGVyZSBpcyBubyB0aGlyZCBndWFyZCBvbiB0aGF0IGxpbmUgc2VnbWVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIHNlY3VyaXR5IHJlYXNvbnMsIHRoZSBndWFyZHMgbXVzdCBiZSBwbGFjZWQgc28gdGhhdCBlYWNoIGd1YXJkIHNlZXMgdGhlIG90aGVyIHR3by4gSG93IG1hbnkgd2F5cyBjYW4gdGhleSBiZSBwbGFjZWQ/Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDIwKSwgdGhlIG51bWJlciBvZiB0cmVuY2hlcy4gRWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIHRoZSBkZXNjcmlwdGlvbiBvZiBvbmUgdHJlbmNoOiBmb3VyIHBvc2l0aXZlIGludGVnZXJzIFgxLCBZMSwgWDIsIFkyIChhbGwgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEwMDApLCB3aGVyZSBYMSBhbmQgWTEgYXJlIGNvb3JkaW5hdGVzIG9mIG9uZSBlbmQsIHdoaWxlIFgyIGFuZCBZMiBhcmUgY29vcmRpbmF0ZXMgb2YgdGhlIG90aGVyIGVuZCBvZiB0aGUgdHJlbmNoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UcmVuY2hlcyBpbiB0aGUgaW5wdXQgbWF5IG92ZXJsYXAgYW5kIHNoYXJlIGVuZHBvaW50cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiB3YXlzIHRoZSBndWFyZHMgY2FuIGJlIHBsYWNlZCBvbiBhIHNpbmdsZSBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #2 6번