직사각형과 직각삼각형
면접 대비시간 제한1초메모리 제한256 MB
네 검은 점으로 변이 축에 평행한 직사각형(정사각형 제외)을 이루고 흰 세 점으로 직각삼각형을 이루는 서로 다른 칠하기 경우의 수를 센다.
문제
평면 위에 N개의 점이 있고, i번째 점은 (Xi, Yi)에 있다. 같은 위치에 여러 점이 있을 수도 있다. 이 중 네 점을 검은색으로, 다른 세 점을 흰색으로 칠한다. 나머지 N − 7개의 점은 칠하지 않는다.
직사각형은 정사각형이 아닌 사각형이다.
직각삼각형은 내각 중 하나가 정확히 90도인 삼각형이다.
검은색 점 네 개가 직사각형의 꼭짓점이고 흰색 점 세 개가 직각삼각형의 꼭짓점이 되도록 점을 색칠하는 방법의 수를 구하시오. 두 도형 모두 넓이가 양수여야 한다.
입력
첫째 줄에 정수 N이 주어진다. (7 ≤ N ≤ 24)
둘째 줄에 N개의 정수 X1, ..., XN이 주어진다. (−229 ≤ Xi ≤ 229)
셋째 줄에 N개의 정수 Y1, ..., YN이 주어진다. (−229 ≤ Yi ≤ 229)
출력
직사각형 하나와 직각삼각형 하나를 고르는 방법의 수를 한 줄에 출력한다.
힌트
직사각형을 만들 수 있는 방법은 점 1, 2, 7, 8을 쓰는 것뿐이다. 남은 네 점 중에서 직각삼각형을 만드는 방법은 두 가지다.
