삼각형
시간 제한2초메모리 제한512 MB
평면 위 N개의 점과 Q개의 질의 점이 주어질 때, 질의 점을 한 꼭짓점으로 하고 주어진 점 두 개를 나머지 꼭짓점으로 하는 삼각형 중 두 변의 길이 차가 0.0001 미만인 것의 개수를 센다.
문제
평면 위에 좌표가 소수인 서로 다른 N개의 점이 주어진다. Q개의 질의를 처리하는 프로그램을 작성하시오. 각 질의는 두 소수 x와 y로 주어진다. 각 질의마다 좌표가 (x, y)인 점을 한 꼭짓점으로 하고 나머지 두 꼭짓점이 주어진 N개의 점 중 서로 다른 두 점인 엡실론 이등변 삼각형의 개수를 계산해야 한다.
삼각형의 두 변의 길이 차의 절댓값이 0.0001보다 작으면 그 삼각형을 엡실론 이등변 삼각형이라고 한다. 이때 삼각형의 두 꼭짓점이 서로 다른 점일 필요는 없고, 세 꼭짓점이 일직선 위에 있지 않을 필요도 없다.
입력
입력의 첫째 줄에는 정수 N과 Q가 주어진다. 다음 N개의 줄에는 주어진 점의 좌표인 두 소수가 각각 주어진다. 그다음 Q개의 줄에는 각각 질의로 주어지는 점의 좌표인 두 소수가 주어진다.
출력
프로그램은 Q개의 줄을 출력해야 하며, 각 줄에는 입력 순서대로 각 질의의 답을 나타내는 정수 하나를 출력한다.
제한
- 0 < N ≤ 1000
- 0 < Q ≤ 1000
모든 점의 좌표는 [0; 1 000 000] 범위의 소수이며, 소수점과 함께 소수 부분이 최대 9자리까지 주어진다.
테스트 데이터에는 엡실론 이등변 삼각형으로 두 가지 이상의 방식으로 셀 수 있는 삼각형이 없다. 즉, 삼각형의 변의 길이를 a, b, c라 하고 a ≥ b ≥ c라 할 때, a-b < 0.0001과 b-c < 0.0001이 동시에 성립할 수 없다.
테스트 데이터에서는 엡실론 이등변 삼각형에 대한 다음 정의들이 모두 같은 결과를 낸다:
- 두 변의 길이 차의 절댓값이 0.0001보다 작다
- 두 변의 길이 차의 절댓값이 0.0003보다 작다
- 두 변의 길이 차의 절댓값이 0.00003보다 작다
힌트
점 (5, 5)에 대한 엡실론 이등변 삼각형은 다음과 같다:
- (5, 5), (0, 5), (5, 0)
- (5, 5), (3, 4), (4, 3)
점 (0, 0)에 대한 엡실론 이등변 삼각형은 다음과 같다:
- (0, 0), (0, 5), (3, 4)
- (0, 0), (0.5), (4, 3)
- (0, 0), (0, 5), (5, 0)
- (0, 0), (3, 4), (4, 3)
- (0, 0), (3, 4), (5, 0)
- (0, 0), (4, 3), (5, 0)
점 (0, 9)에 대해서는 엡실론 이등변 삼각형이 없다.