4105 유클리드

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

4105번: 유클리드

---

기하학 문제를 풀 때 연습장을 쓰게 되더라. 그래도 다른 카테고리의 문제들은 애매한 부분이 남아 문제를 완벽히 풀었다는 생각이 잘 들지 않는데, 이런 문제들은 수식으로 정확히 표현되니까 정말 좋다.

접근

일단 삼각형과 평행사변형의 넓이가 같다는 조건을 쓰기 위해 삼각형의 넓이를 구해야 한다.

 

세 변만 주어졌으므로 헤론의 공식을 통해 삼각형의 넓이를 구해보았다.

$$\triangle DEF = \sqrt{s(s-a)(s-b)(s-c)}, s = {{a+b+c}\over 2} \\ a = |\overrightarrow{DE}|, b = |\overrightarrow{EF}|, c = |\overrightarrow{DF}|$$

이 넓이가 평행사변형의 넓이과 같다는데, 평행사변형의 넓이를 구하는데에는 두 가지 공식이 있다.

 

하나는 밑변 * 높이이고, 다른 하나는 두 변 a, b를 이용하는 건데,  $a\times b\times sinθ$이다.

 

이 문제에서 선분 AB와 직선 AC가 주어졌기 때문에 후자가 적절하다. 전자로 했다가 30분동안 끙끙대고 후자를 떠올렸다.

 

평행사변형의 넓이를 S라고 한다면,

$$S = |\overrightarrow{AB}| \times |\overrightarrow{AH}| \times sin\theta$$

 

$\overrightarrow{AH}$는 임의의 점 $H$와 점 $A$의 길이인데 아직 모르고, $|\overrightarrow{AB}|$는 알고 있다. $sinθ$는 내적 공식을 통해 유도해낼 수 있다.

$$|\overrightarrow{AB} \cdot \overrightarrow{AC} | = |\overrightarrow{AB}||\overrightarrow{AC}|cos\theta \\ cos\theta = {|\overrightarrow{AB} \cdot \overrightarrow{AC}|\over{|\overrightarrow{AB}||\overrightarrow{AC}|}} \\ sin\theta = \sqrt{1 - {cos^2\theta}}$$

 

여기서 얻은 $sinθ$를 평행사변형의 넓이에 대입하면 $|\overrightarrow{AH}|$를 얻을 수 있다.

 

이제 $H$의 좌표를 구한 다음 $\overrightarrow{OH}$에 $\overrightarrow{AB}$를 더하면 $\overrightarrow{OG}$,즉 점 $G$도 얻을 수 있다.

$H$는 직선 $AC$위에 있다. 점 $A$로부터 x축에 평행한 임의의 직선을 놓고 점 $H$, 점 $C$에서 내린 수선의 발을 $H', C'$라고 할 때 $\triangle{ACC'}$와 $\triangle{AHH'}$는 닮음인 것을 볼 수 있다. 이 말은 $|\overrightarrow{AC}| : |\overrightarrow{AH}| = |\overrightarrow{AC'}| : |\overrightarrow{AH'}|$라는 것이다.

 

이 비율에 관한 관계를 $|\overrightarrow{AH'}|$에 대해 정리하면,

$$|\overrightarrow{AH'}| = {|\overrightarrow{AC'}||\overrightarrow{AH}| \over{|\overrightarrow{AC}|}}$$

 

이렇게 $|\overrightarrow{AH'}|$를 구했는데 이건 점 $A$의 x좌표로부터 얼마나 떨어져 있는지를 나타낸다. 그러므로 점 $A$의 x좌표값을 더해주면 H의 x좌표를 얻을 수 있다.

 

동일하게 점 $A$로부터 y축에 평행한 임의의 직선을 놓고 점 $H$, 점 $C$에서 내린 수선의 발을 $H'', C''$라고 한 후 직전의 공식을 적용하면 H의 좌표는 다음과 같다.

$$A(x_a, y_a), \therefore H = (x_a + {|\overrightarrow{AC'}||\overrightarrow{AH}|\over{|\overrightarrow{AC}|}}, y_a + {|\overrightarrow{AC''}||\overrightarrow{AH}|\over{|\overrightarrow{AC}|}})$$

점 $G$의 좌표도 곧바로 구해진다.

$$A(x_a, y_a), B(x_b, y_b), H(x_h, y_h), \therefore G = (x_h + x_b - x_a, y_h + y_b - y_a )$$

미흡했던 점

평행사변형 넓이를 구하는 공식이 여러가지가 있었는데 각도를 쓰는 공식을 떠올리지 못했다. 

 

1시간 반 정도 걸려서 풀었는데 공식을 완벽하게 정리하지 못한 상태로 허겁지겁 답을 제출하려 했었다. 특히 마지막 H의 좌표를 구할 때 벡터 덧셈을 헷갈려했었다. 

---

#include <cmath>
#include <iostream>
#define ABS(X) ((X) > 0 ? (X) : -(X))
struct Point {
  double x, y;
};
double d(Point p1, Point p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
bool isZero(Point p1) { return p1.x == 0 && p1.y == 0; }
int main() {
  Point A, B, C, D, E, F;
  while (1) {
    scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf", &A.x, &A.y, &B.x,
          &B.y, &C.x, &C.y, &D.x, &D.y, &E.x, &E.y, &F.x, &F.y);
    if (isZero(A) && isZero(B) && isZero(C) && isZero(D) && isZero(E) &&
        isZero(F)) {
      return 0;
    }
    double DE = d(D, E), EF = d(E, F), FD = d(F, D), s = (DE + EF + FD) / 2,
           DEF = sqrt(s * (s - DE) * (s - EF) * (s - FD));
    Point ABvec = {B.x - A.x, B.y - A.y}, ACvec = {C.x - A.x, C.y - A.y};
    double cosTheta =
               ABS(ABvec.x * ACvec.x + ABvec.y * ACvec.y) / (d(A, B) * d(A, C)),
           sinTheta = sqrt(1.0 - pow(cosTheta, 2)),
           AH = DEF / (d(A, B) * sinTheta);
    Point H = {A.x + (C.x - A.x) * (AH / d(A, C)),
               A.y + (C.y - A.y) * (AH / d(A, C))},
          G = {H.x + B.x - A.x, H.y + B.y - A.y};
    printf("%.3lf %.3lf %.3lf %.3lf\n", G.x, G.y, H.x, H.y);
  }
}

모든 입력이 0일 경우를 처리하기 위해 함수를 사용했다.