백준 1485 자바 - 정사각형 (BOJ 1485 JAVA)

[ 문제 보기 ]

[ 코드 보기(깃헙) ]

 

 

[ 틀린 경우 ]

  처음엔 아래와 같이 축에 평핸한 정사각형을 찾는줄 알았다.

그래서 예를들어 입력이

1

1 1

1 2

2 1

2 2

와 같다면, 사실 좌측이 x축인지 우측이 x축인지는 안알려줬지만 상관없이 좌측이 2종류고, 우측이 2종류이며 각각 2번씩 나왔고, 좌측의 2종류의 차이와 우측의 2종류의 차이가 동일하다면 정사각형으로 판단하도록 했다. 이 코드는 틀렸다.

 

 

[ 해설 ]

그렇다면 아래와 같이 정사각형이 기울어 있는 경우까지 찾을 수 있어야 한다.

 

 

1. 그래도 딱히 어려울건 없는데, 그냥 4개의 점을 입력받고 나올 수 있는 모든 경우의 길이를 구해본다. 4개에서 2개를 순서없이 골라야하니, 4C2 = 4P2 / 2! = 4*3/2 = 6가지만 구해보면 된다.

위와 같이 각 변의 길이와, 대각선의 길이까지가 포함된다. 그림은 이렇게 그렸지만, 사실 입력받은 4개의 점이 위와 같이 순서대로 들어올리는 없다. 예를들어 

1

1 1

2 2

1 2

2 1

과 같은 순서로 들어올 수도 있다. 하지만 그래도 상관없다. 어차피 모든 경우를 보는거고, 결국 알아야 될 것은 6개의 길이를 모두 구해보고 동일한 4개의 길이(각 변의 길이)와, 또다른 동일한 2개의 길이(대각선의 길이)만 있으면 된다. 대각선까지 알아야 하는 이유는 마름모를 제외하기 위해서이다.

 

그럼 로직은 다음과 같다.

A. 4개의 점을 입력받는다. (코드의 24line)

B. 모든 점에서 모든 점 사이의 모든 경우에 대한 6가지 경우의 길이를 구한다. (코드의 30line)

C. 6개짜리를 정렬한다. -> 4개의 동일 길이, 2개의 동일 길이를 찾기 편하도록. (코드의 33line)

D. 정렬된 6개에서 처음 4개가 동일하고, 마지막 2개가 동일한지 확인한다. (코드의 34line) -> 정사각형에서 대각선은 무조건 각 변의 길이보다 길다.

 

추가팁이라면, 원래 알고리즘에서 소수 연산의 비교는 엄청 조심해서 해야한다. 분수로 표현해서 진행하는게 아니라 항상 오차가 생길 수 있다. 따라서 최대한 소수 사용을 지양하는게 좋다. 길이도 원래는 sqrt( (x2-x1)^2 + (y2-y1)^2 )으로 구해야하지만, sqrt(square root)는 제외하고 길이 차이의 제곱의 합 까지만 하면 정수로 비교가능하다.