#18778 Equilateral Triangles

문제요약.

300*300 grid에서 거리의 정의를 manhatan distance로 했을때 정삼각형의 개수를 구하여라.

 

 

 

우선 유클리드 좌표게에서 정수 좌표 3개의 꼭짓점을 가지는 정삼각형은 존재하지 않는다. tan 60이 무리수이기 때문.

따라서 이 문제에서는 맨해튼 거리로 변형되었는데, 접근 방식은 다음과 같다.

 

일단 점 2개가 일직선인 경우는 예외처리 했다. 이는 간단한 sweeping으로 예외 처리 할 수 있다.

이제 3점의 x와 y좌표는 전부 distinct하다고 가정하자.

 

우리는 이제 이런걸 생각해보자.

어떤 점 3개를 뽑았을때 이 3개의 점이 정삼각형이 되는지를 어떻게 판정할 지를 생각해보면 되자.

 

우선 이 3점을 x좌표로 정렬하자.

그렇다면, x좌표로 정렬하고 봤을때, y좌표의 대소관계에 따라 6가지 경우로 나뉘어진다.

 

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

(이 permutation은 y좌표의 크기 순서이다.)

 

그렇다면 

1 2 3

3 2 1 은 무시해도 되고, 나머지 경우를 살펴보자.

 

1 3 2 경우부터 살펴보자.

 

결론적으로 b=d=a+c가 된다.

나머지 permutation도 저걸 돌린거기 때문에 4방향에 대해서 탐색해주면 된다.

 

여기서 prefix sum이나 map같은 걸로 수를 빠르게 세주면 되는데, 안해도 뭔가 커팅해도 될거같아서 brute force 했는데 통과했다. ㅋㅋ!