1485 정사각형

https://www.acmicpc.net/problem/1485

1485번: 정사각형

---

생각한 과정

정사각형이 되는 조건과 점의 입력순서를 따지느라 매우 애를 먹었다.

 

점 4개가 주어졌을 때 정사각형이 되는지 안되는지 판단하는 문제다.

 

처음엔 이렇게 생각했었다. 각 변의 길이가 같고 모든 각의 길이가 90도이니, 변의 길이를 모두 대조하고 변을 벡터로 생각해 내적시켰을 때 0이면 정사각형이 되지 않나?

 

맞는 말이라고 생각해 그대로 했으나 이유를 모른채 실패했다. 무엇보다도 코드 길이가 너무 길어지더라...

 

문제를 다시 읽어보고 반례를 만들어 넣어보다가 데이터 입력부분에서 내가 생각한 방향대로 점이 주어지지 않을 수 있다는 것을 발견했다.

 

즉, 입력된 점들을 간단하게 정렬하여 내가 생각한 배열로 만든 후 나름의 판별식으로 검증해야했다.

위 사진처럼 x좌표값이 작은 순서대로 정렬했다. 그 후에 검증하는 방법을 살펴봤는데, 코드가 매우 길고 복잡하다고 느껴져 다시 생각해보았다.

 

정사각형은 대각선의 길이가 모두 같고 서로 직교한다는 성질을 갖고 있다. 이 성질을 보자마자 훨씬 간단하게 정리할 수 있겠다고 생각했다. 

 

위의 사진을 참고하면, 정사각형이 되기 위해서는 1번과 4번, 2번과 3번을 잇는 각 선이 직교하고 길이가 같아야 한다.

 

직교한다는 것은 두 대각선(벡터)을 내적했을 때 0이라는 말이고, 길이가 같다는 말은 두 대각선(벡터)을 스스로 내적했을 때 길이가 같다는 말이다.

---

미흡했던 것

여기까지 했음에도 틀렸는데, 데이터의 범위가 -10만 ~ 10만이었다. 스스로 내적했을 때 int의 범위를 넘어간다.

데이터의 범위 또한 놓치지 말아야하는데 자꾸 실수한다. :(

 

또 틀린 이유는 정렬에 문제가 있었다.

x좌표가 같은 경우엔?

위 사진처럼 x좌표가 같은 경우엔 별다른 조건이 없었기 때문에 3번과 4번의 순서가 바뀌었다. 따라서 원했던 순서대로 정렬이 되어지지 않았다. x좌표가 같을 땐, y좌표가 더 작은 값이 앞으로 오도록 해야했다.

---

나는 개인적으로 좌표문제가 나오면 구조체를 쓴다. 함수에게 넘겨주는 인자가 줄어들어서 마음이 편하다.

#include <iostream>
struct Point {
  int x, y;
};
long long dot(Point vec1, Point vec2) {
  return (long long)vec1.x * vec2.x + (long long)vec1.y * vec2.y;
}
int main() {
  int T;
  scanf("%d", &T);
  for (int i = 0; i < T; i++) {
    Point p[4];
    for (int j = 0; j < 4; j++) {
      scanf("%d%d", &p[j].x, &p[j].y);
    }
    for (int j = 0; j < 3; j++) {
      for (int k = j + 1; k < 4; k++) {
        if (p[j].x > p[k].x || (p[j].x == p[k].x && p[j].y > p[k].y)) {
          Point t = p[j];
          p[j] = p[k];
          p[k] = t;
        }
      }
    }
    Point d1 = {p[3].x - p[0].x, p[3].y - p[0].y},
          d2 = {p[2].x - p[1].x, p[2].y - p[1].y};

    printf("%d\n", dot(d1, d2) == 0 && dot(d1, d1) == dot(d2, d2));
  }
}