10255번 교차점

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

Keywords: Geometry, Line Segment Intersection

이 문제는 선분과 선분의 교점을 헤아리는 문제이다. 좌표들이 모두 정수로 주어지기 때문에 조금 더 간소한 방법을 사용해볼 수도 있겠으나, 여기서는 Line intersection도 복습할 겸 모든 좌표가 실수로 주어진다고 가정하고 풀이하였다.

풀이의 과정은 아래와 같다.

STEP 1. 사각형을 4개의 line segment로 취급한다.
STEP 2. 사각형의 4개 line segment와 주어진 또 다른 line segment의 교점을 찾아준다.
- 이 때, 사각형 line segment의 끝 점에서 교점을 갖는 경우도 별도로 구분하지 않고 세어준다.
STEP 3. 사각형의 각 꼭지점이 주어진 line segment 위에 있는지 판단한다.
STEP 4. STEP 2에서 세어준 교점의 수에서 STEP 3에서 세어준 line segment 위 꼭지점 수를 빼준다.
- 이들은 STEP 2에서 각 변의 끝점에서 교차하는 경우를 별도로 처리하지 않아서 중복으로 세어진 점들이기 때문이다.

이 외의 모든 과정은 Line intersection를 따르고 있기 때문에 straight-forward하다.

다만, 실수로 좌표들을 다루다보니 Vector2D::bool operator<(const Vector2D& rhs) const의 구현에서 WA를 받도록 만드는 실수가 있었다. 보통 같으면, 아마도 아래와 같이 구현할 것이다.

bool Vector2D::operator<(const Vector2D& rhs) const {
  if (x_ != rhs.x_) {
    return x_ < rhs.x_;
  }
  return y_ < rhs.y_;
}

그런데, 위의 코드는 Vector2D{48, -53} < Vector{48, -33}를 false로 evaluation하는 경우가 있다. 이는 double 타입에 대하여 정의된 != operator가 부동소수점 오차에 영향을 받을 수 밖에 없기 때문이다. 따라서, 이를 아래 코드에서 볼 수 있듯이 적당한 Epsilon을 정의하여 처리해주었다.

아래는 솔루션이다.

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

using namespace std;

// Inputs.
int T;
double XMIN, YMIN, XMAX, YMAX;
double X1, Y1, X2, Y2;

// Solution.
constexpr double kEpsilon = 1e-7;

class Vector2D {
 public:
  Vector2D() = default;
  Vector2D(double x, double y) : x_(x), y_(y) {}

  double x() const { return x_; }
  double y() const { return y_; }

  double GetNorm() const { return sqrt(GetSquaredNorm()); }
  double GetSquaredNorm() const { return x_ * x_ + y_ * y_; }
  double GetDot(const Vector2D& rhs) const { return x_ * rhs.x_ + y_ * rhs.y_; }
  double GetDet(const Vector2D& rhs) const { return x_ * rhs.y_ - y_ * rhs.x_; }

  Vector2D operator+(const Vector2D& rhs) const {
    return Vector2D(x_ + rhs.x_, y_ + rhs.y_);
  }
  Vector2D operator-(const Vector2D& rhs) const {
    return Vector2D(x_ - rhs.x_, y_ - rhs.y_);
  }
  Vector2D operator*(double scale) const {
    return Vector2D(x_ * scale, y_ * scale);
  }
  bool operator<(const Vector2D& rhs) const {
    if (abs(x_ - rhs.x_) >= kEpsilon) {
      return x_ < rhs.x_;
    }
    return y_ < rhs.y_;
  }
  bool operator<=(const Vector2D& rhs) const {
    return ((*this < rhs) || (*this == rhs));
  }
  bool operator==(const Vector2D& rhs) const {
    return (rhs - *this).GetSquaredNorm() < kEpsilon;
  }
  bool operator!=(const Vector2D& rhs) const { return !(*this == rhs); }

 private:
  double x_;
  double y_;
};

class Segment2D {
 public:
  Segment2D() = default;
  Segment2D(const Vector2D& src, const Vector2D& dst) : src_(src), dst_(dst) {
    if (dst_ < src_) {
      swap(src_, dst_);
    }
  }

  const Vector2D& src() const { return src_; }
  const Vector2D& dst() const { return dst_; }

  Vector2D GetDirection() const { return dst_ - src_; }

  bool IsColinear(const Segment2D& rhs) const {
    return abs(GetDirection().GetDet(rhs.GetDirection())) < kEpsilon;
  }
  bool IsPointOnSegment(const Vector2D& point) const {
    return IsColinear(Segment2D(dst_, point)) && src_ <= point && point <= dst_;
  }
  // Returns the number of intersections between this segment and rhs. If the
  // number of intersections is infinite, returns -1.
  int CountIntersections(const Segment2D& rhs) const {
    const auto dir_0 = GetDirection();
    const auto dir_1 = rhs.GetDirection();
    const auto det = dir_0.GetDet(dir_1);

    if (abs(det) < kEpsilon) {
      if (!IsColinear(Segment2D(dst_, rhs.src())) ||
          (dst_ < rhs.src() || rhs.dst() < src_)) {
        return 0;
      } else if ((src_ == rhs.dst() && dst_ != rhs.src()) ||
                 (src_ != rhs.dst() && dst_ == rhs.src())) {
        return 1;
      } else {
        return -1;
      }
    } else {
      const auto scale = (rhs.src() - src_).GetDet(dir_1) / det;
      const auto p = src_ + dir_0 * scale;
      return IsPointOnSegment(p) && rhs.IsPointOnSegment(p) ? 1 : 0;
    }
  }

 private:
  Vector2D src_;
  Vector2D dst_;
};

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

  // Read inputs.
  cin >> T;
  while (T--) {
    cin >> XMIN >> YMIN >> XMAX >> YMAX;
    cin >> X1 >> Y1 >> X2 >> Y2;

    vector<Segment2D> rectangle;
    rectangle.emplace_back(Vector2D(XMIN, YMIN), Vector2D(XMIN, YMAX));
    rectangle.emplace_back(Vector2D(XMIN, YMAX), Vector2D(XMAX, YMAX));
    rectangle.emplace_back(Vector2D(XMAX, YMAX), Vector2D(XMAX, YMIN));
    rectangle.emplace_back(Vector2D(XMAX, YMIN), Vector2D(XMIN, YMIN));

    Segment2D segment(Vector2D(X1, Y1), Vector2D(X2, Y2));

    // Solve.
    int num_of_corners = 0;
    num_of_corners += segment.IsPointOnSegment({XMIN, YMIN}) ? 1 : 0;
    num_of_corners += segment.IsPointOnSegment({XMIN, YMAX}) ? 1 : 0;
    num_of_corners += segment.IsPointOnSegment({XMAX, YMAX}) ? 1 : 0;
    num_of_corners += segment.IsPointOnSegment({XMAX, YMIN}) ? 1 : 0;

    int num_of_intersections = 0;
    for (const auto& side : rectangle) {
      const auto query = segment.CountIntersections(side);
      if (query == -1) {
        num_of_intersections = -1;
        break;
      } else {
        num_of_intersections += query;
      }
    }
    int answer =
        num_of_intersections == -1 ? 4 : num_of_intersections - num_of_corners;
    cout << answer << '\n';
  }

  return 0;
}