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

문제

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

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

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

입력

첫째 줄에 참호의 수 N이 주어진다. (1 ≤ N ≤ 20) 다음 N개 줄에는 참호의 정보가 네 양의 정수 X1, Y1, X2, Y2로 주어진다. 좌표는 모두 1000보다 작거나 같다. (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
W3sicHJvYmxlbV9pZCI6IjMwNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNzBcdWMwYWMgXHVhZTMwXHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjOWQxIFx1YWRmY1x1Y2M5OFx1YzVkMFx1YjI5NCBcdWFkNzBcdWMwYWMgXHVhZTMwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhZDcwXHVjMGFjIFx1YWUzMFx1YzljMFx1YzVkMFx1YjI5NCBcdWNjMzhcdWQ2MzhcdWFjMDAgXHViOWNlXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjYzM4XHVkNjM4XHViMjk0IFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM3NTggXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YmFhOFx1YjM3OFx1YjljMSBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViOWU0XHVjNzdjIFx1YmMyNCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVhZDcwXHVjNzc4XHViNGU0XHVjNzQwIFx1YzdhMFx1Yzc0NCBcdWM3OTBcdWFjZTAsIFx1YWQ3MFx1Yzc3OCBcdWMxMzggXHViYTg1XHVjNzQwIFx1YmMyNFx1YzBjOFx1YjNjNFx1Yjg1ZCBcdWNjMzhcdWQ2MzhcdWI5N2MgXHVhYzEwXHVjMmRjXHVkNTVjXHViMmU0LiBcdWI0NTAgXHVhZDcwXHVjNzc4XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YjgyNFx1YmE3NCwgXHVhZGY4XHViNGU0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NzQgXHViYWE4XHViNDUwIFx1Y2MzOFx1ZDYzOFx1YzU0OFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWIyZTRcdWI5NzggXHVhZDcwXHVjNzc4XHVjNzQwIFx1YWRmOCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNWM2XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViY2Y0XHVjNTQ4IFx1YzBjMVx1Yzc1OCBcdWM3NzRcdWM3MjAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWQ3MFx1Yzc3OFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMTFjXHViODVjXHViOTdjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZDcwXHVjNzc4XHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIFx1YmE4NyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMzhcdWQ2MzhcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2MzOFx1ZDYzOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHViMTI0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggWDEsIFkxLCBYMiwgWTJcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViYWE4XHViNDUwIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gKFgxLCBZMSlcdWFjZmMgKFgyLCBZMilcdWIyOTQgXHVjYzM4XHVkNjM4XHVjNzU4IFx1YzU5MSBcdWIwNWQgXHVjODEwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjMzhcdWQ2MzhcdWIyOTQgXHVhY2I5XHVjZTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjA1ZCBcdWM4MTBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkNzBcdWM3NzhcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwNTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVFJBXHUwMTdkQSIsImRlc2NyaXB0aW9uIjoiPHA+TmVhciBhIG1pbGl0YXJ5IGJhc2UgdGhlcmUgaXMgYSBzeXN0ZW0gb2YgdHJlbmNoZXMsIG1vZGVsZWQgYXMgbGluZSBzZWdtZW50cyBvbiBhIHBsYW5lLiBEdXJpbmcgbmlnaHR0aW1lLCB3aGVuIG1vc3Qgc29sZGllcnMgYXJlIGZhc3QgYXNsZWVwLCB0aHJlZSBndWFyZHMgc3RhbmQgd2F0Y2ggb2YgdGhlIHRyZW5jaGVzLiBUd28gZ3VhcmRzIGNhbiBzZWUgZWFjaCBvdGhlciBpZiB0aGVyZSBpcyBhIHRyZW5jaCAob3IgYSByb3cgb2YgdHJlbmNoZXMpIGFsb25nIHRoZSBlbnRpcmUgc3RyYWlnaHQgbGluZSBzZWdtZW50IGJldHdlZW4gdGhlbSBhbmQgdGhlcmUgaXMgbm8gdGhpcmQgZ3VhcmQgb24gdGhhdCBsaW5lIHNlZ21lbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBzZWN1cml0eSByZWFzb25zLCB0aGUgZ3VhcmRzIG11c3QgYmUgcGxhY2VkIHNvIHRoYXQgZWFjaCBndWFyZCBzZWVzIHRoZSBvdGhlciB0d28uIEhvdyBtYW55IHdheXMgY2FuIHRoZXkgYmUgcGxhY2VkPyZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAyMCksIHRoZSBudW1iZXIgb2YgdHJlbmNoZXMuIEVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyB0aGUgZGVzY3JpcHRpb24gb2Ygb25lIHRyZW5jaDogZm91ciBwb3NpdGl2ZSBpbnRlZ2VycyBYMSwgWTEsIFgyLCBZMiAoYWxsIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMDAwKSwgd2hlcmUgWDEgYW5kIFkxIGFyZSBjb29yZGluYXRlcyBvZiBvbmUgZW5kLCB3aGlsZSBYMiBhbmQgWTIgYXJlIGNvb3JkaW5hdGVzIG9mIHRoZSBvdGhlciBlbmQgb2YgdGhlIHRyZW5jaC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VHJlbmNoZXMgaW4gdGhlIGlucHV0IG1heSBvdmVybGFwIGFuZCBzaGFyZSBlbmRwb2ludHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2Ygd2F5cyB0aGUgZ3VhcmRzIGNhbiBiZSBwbGFjZWQgb24gYSBzaW5nbGUgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d