07694번 Triangle

Problem link: https://www.acmicpc.net/problem/7694

Keywords: Geometry, Pick's Theorem

이 블로그에서는 시간이 날 때마다 이전 블로그에서 풀었던 문제들을 다시 풀어서 정리하고 있다. 그런데, 그새 조금 더 늙었기 때문인지 업데이트가 참 더디다. 아마도, 대학 시절에는 없었던 결혼생활과 두 아이의 육아라는 과업이 영향이 있는 것 같다. 그래서, 뭔가 처방이 필요하지 않나라는 생각을 해보았다. 결정한 처방은 “그냥 재미있는 것 풀자” 이다.

나는 대학교 때부터 computational geometry나 graph theory를 참 좋아했었다. 하지만, acmicpc나 코딩 인터뷰에서 해당 분야의 알고리즘을 출제하는 경우는 극히 드물 수 밖에 없음을 교활하게도 깨닫고 있었고, 따라서 자연스레 다른 재미 없어하는 알고리즘들에 집중했던 것 같다. 이제는 acmicpc나 코딩 인터뷰를 준비하는 것도 아니고, 회사 스트레스를 풀려고 문제를 풀고 있으니 그냥 좋아하던 것을 풀어보련다.

이 문제는 Pick’s Theorem을 쓰면 쉽게 풀 수 있다.

다만, Pick's Theorem을 사용하기 위해서 아래 bullet의 helper function들이 필요한데 크게 어렵지는 않으니 쉽게 구현할 수 있다.

Triangle의 넓이 구하기
- 각 변을 순서대로 순회하면서 외적의 합을 구하고, 그 절대값의 절반을 취해주면 된다.
Triangle의 exterior에 있는 격자점 수 구하기
- 최대공약수를 잘 활용해주면 역시 쉽게 풀 수 있다.

아래는 솔루션이다.

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

// Inputs.
struct Point2D {
  int x;
  int y;
};

struct Polygon2D {
  vector<Point2D> exterior;
};

// Solution.
int ComputeGcd(int a, int b) {
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

double ComputeArea(const Polygon2D& polygon) {
  double sum = 0.0;
  for (std::size_t idx = 0; idx < polygon.exterior.size(); ++idx) {
    const auto& from = polygon.exterior[idx];
    const auto& to = polygon.exterior[(idx + 1) % polygon.exterior.size()];
    sum += from.x * to.y - from.y * to.x;
  }
  return 0.5 * abs(sum);
}

int CountLatticePointsOnExterior(const Polygon2D& polygon) {
  int ret = 0;
  for (std::size_t idx = 0; idx < polygon.exterior.size(); ++idx) {
    const auto& from = polygon.exterior[idx];
    const auto& to = polygon.exterior[(idx + 1) % polygon.exterior.size()];
    const auto dx = abs(from.x - to.x);
    const auto dy = abs(from.y - to.y);
    if (dx == 0) {
      ret += dy;
    } else if (dy == 0) {
      ret += dx;
    } else {
      auto gcd = ComputeGcd(dx, dy);
      ret += dx / (dx / gcd);
    }
  }
  return ret;
}

int Solution(const Polygon2D& polygon) {
  double area = ComputeArea(polygon);
  int lattice_points_on_exterior = CountLatticePointsOnExterior(polygon);
  return static_cast<int>(area - lattice_points_on_exterior / 2 + 1);
}

int main(void) {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read inputs.
  while (true) {
    Polygon2D polygon3};
    cin >> polygon.exterior[0].x >> polygon.exterior[0].y >>
        polygon.exterior[1].x >> polygon.exterior[1].y >>
        polygon.exterior[2].x >> polygon.exterior[2].y;
    if (polygon.exterior[0].x == 0 && polygon.exterior[0].y == 0 &&
        polygon.exterior[1].x == 0 && polygon.exterior[1].y == 0 &&
        polygon.exterior[2].x == 0 && polygon.exterior[2].y == 0) {
      break;
    } else {
      // Solve.
      cout << Solution(polygon) << '\n';
    }
  }

  return 0;
}