This documentation is automatically generated by online-judge-tools/verification-helper

:warning: src/geometric.cr

Depends on

Code

require "./geometric/*"
# require "./geometric/*"
# require "./real"
require "big"

alias Real = BigFloat
EPS = Real.new(1e-12)

struct Real
  def <=>(other : Real)
    {% if Real == BigFloat %}
      if previous_def(other - EPS) < 0
        -1
      elsif previous_def(other + EPS) > 0
        1
      else
        0
      end
    {% else %}
      if self < other - EPS
        -1
      elsif self > other + EPS
        1
      else
        0
      end
    {% end %}
  end

  def sign : Int32
    self < -EPS ? -1 : self > EPS ? 1 : 0
  end

  def to_radian
    self * Math::PI / 180
  end

  def to_degree
    self * 180 / Math::PI
  end

  def self.scan(scanner, io : IO) : self
    Real.new scanner.s(io)
  end
end

# require "./object/*"
module Geometric
  struct Circle
    property center : Vec2, radious : Real

    def initialize(center : Vec2, radious)
      @center, @radious = center, Real.new(radious)
    end

    def initialize(x, y, radious)
      initialize(Vec2.new(x, y), radious)
    end

    def self.scan(s, io : IO) : self
      new Real.scan(s, io), Real.scan(s, io), Real.scan(s, io)
    end

    delegate x, y, to: center

    {% for op in %w[+ - * /] %}
      def {{op.id}}(other : Vec2)
        Circel.new(x {{op.id}} other.x, y {{op.id}} other.y, radious)
      end

      def {{op.id}}(other : Real)
        Circle.new(x {{op.id}} other, y {{op.id}} other, radious)
      end
    {% end %}

    def area : Real
      radious * radious * Math::PI
    end

    def contains?(v : Vec2)
      ((v - center).length <=> radious) < 0
    end

    def inspect(io : IO)
      io << '(' << center << ", " << radious << ')'
    end
  end
end

# require "../real"

# require "./vec2"
# require "../real"

module Geometric
  struct Vec2
    include Comparable(Vec2)

    property x : Real, y : Real

    def self.zero
      Vec2.new(Real.zero, Real.zero)
    end

    def initialize(x, y)
      @x, @y = Real.new(x), Real.new(y)
    end

    def self.scan(scanner, io : IO) : self
      Vec2.new(scanner.f(io), scanner.f(io))
    end

    def +
      self
    end

    def -
      Vec2.new(-x, -y)
    end

    {% for op in %w[+ - * /] %}
      def {{op.id}}(other : Vec2)
        Vec2.new(x {{op.id}} other.x, y {{op.id}} other.y)
      end

      def {{op.id}}(other)
        Vec2.new(x {{op.id}} other, y {{op.id}} other)
      end
    {% end %}

    def <=>(other : Vec2)
      x_cmp = x <=> other.x
      if x_cmp != 0
        x_cmp
      else
        y <=> other.y
      end
    end

    def [](index : Int)
      return x if index == 0
      return y if index == 1
      raise IndexError.new
    end

    def length : Real
      Math.hypot(x, y)
    end

    def dot(other : Vec2) : Real
      x * other.x + y * other.y
    end

    def cross(other : Vec2) : Real
      x * other.y - y * other.x
    end

    def angle : Real
      Real.new Math.atan2(y, x)
    end

    def rotate(rad : Real) : Vec2
      c, s = Math.cos(rad), Math.sin(rad)
      Vec2.new(x * c - y * s, x * s + y * c)
    end

    def to_tuple
      {x, y}
    end

    def inspect(io : IO)
      io << '(' << x << ", " << y << ')'
    end
  end
end

module Geometric
  private module LineBase
    getter begin : Vec2, end : Vec2

    def initialize(@begin, @end)
    end

    def initialize(begin_x, begin_y, end_x, end_y)
      @begin = Vec2.new(begin_x, begin_y)
      @end = Vec2.new(end_x, end_y)
    end

    def +(v : Vec2)
      self.class.new(@begin + v, @end + v)
    end

    def -(v : Vec2)
      self.class.new(@begin - v, @end - v)
    end

    def vec
      @end - @begin
    end

    def counter_vec
      @begin - @end
    end

    def parallel?(other : LineBase)
      vec.cross(other.vec).sign == 0
    end

    def orthogonal?(other : LineBase)
      vec.dot(other.vec).sign == 0
    end

    def to_tuple
      {@begin, @end}
    end

    def inspect(io : IO) : Nil
      io << '(' << @begin << ", " << @end << ')'
    end
  end

  struct Line
    include LineBase

    def self.scan(s, io : IO) : self
      new Real.scan(s, io), Real.scan(s, io), Real.scan(s, io), Real.scan(s, io)
    end
  end

  struct Segment
    include LineBase

    def self.scan(scanner, io : IO) : self
      new Real.scan(s, io), Real.scan(s, io), Real.scan(s, io), Real.scan(s, io)
    end
  end
end

module Geometric
  class Polygon < Array(Vec2)
    def initialize(points : Array(Vec2))
      initialize(points.size)
      concat points
    end

    def initialize
      super
    end

    def initialize(initial_capacity : Int)
      super
    end

    def initialize(size : Int, &block : Int32 -> Vec2)
      initialize(size)
      size.to_i.times do |i|
        self << yield i
      end
    end

    def after(i : Int32) : Vec2
      self[i != size - 1 ? i + 1 : 0]
    end

    def area : Real
      (0...size).sum { |i|
        self[i].cross after(i)
      }.abs / 2
    end

    def centroid : Vec2
      sum / size
    end

    def contains?(v : Vec2)
      (0...size).count { |i|
        p1, p2 = {self[i], after(i)}.minmax_by &.y
        (p1.y <=> v.y) <= 0 && (v.y <=> p2.y) < 0 && (p1 - v).cross(p2 - v).sign == -1
      }.odd?
    end

    def convex_hull : Polygon
      result = Polygon.new
      points = sort
      points.each do |point|
        while result.size >= 2 && Geometric.ccw(result[-2], result[-1], point) != -1
          result.pop
        end
        result << point
      end
      t = result.size + 1
      (0...points.size - 1).reverse_each do |i|
        while result.size >= t && Geometric.ccw(result[-2], result[-1], points[i]) != -1
          result.pop
        end
        result << points[i]
      end
      result.pop
      result
    end

    def inspect(io)
      io << self
    end
  end
end

module Geometric
  extend self

  def distance(v1 : Vec2, v2 : Vec2) : Real
    Math.hypot(v1.x - v2.x, v1.y - v2.y)
  end

  def distance(v : Vec2, c : Circle) : Real
    (distance(v, c.center) - c.radious).abs
  end

  def distance(v : Vec2, l : Line) : Real
    (l.vec.cross(v - l.begin) / l.vec.length).abs
  end

  def distance(v : Vec2, s : Segment) : Real
    if s.vec.dot(v - s.begin).sign < 0
      distance(v, s.begin)
    elsif s.counter_vec.dot(v - s.end).sign < 0
      distance(v, s.end)
    else
      distance(v, Line.new(s.begin, s.end))
    end
  end

  def distance(c1 : Circle, c2 : Circle) : Real
    d = distance(c1.center, c2.center)
    r = c1.radious + c2.radious
    if (d <=> r) > 0
      d - r
    elsif (d + c1.radious <=> c2.radious) < 0
      c2.radious - (d + c1.radious)
    elsif (d + c2.radious <=> c1.radious) < 0
      c1.radious - (d + c2.radious)
    else
      Real.zero
    end
  end

  def distance(obj1, obj2) : Real
    distance(obj2, obj1)
  end
end

# require "./real"

# require "./object/*"

# require "./distance"

module Geometric
  extend self

  def intersect?(c1 : Circle, c2 : Circle)
    (distance(c1.center, c2.center) <=> (c1.radious + c2.radious)) < 0
  end

  def intersect?(l1 : Line, l2 : Line)
    !l1.parallel?(l2)
  end

  def intersect?(s1 : Segment, s2 : Segment)
    ccw(s1.begin, s1.end, s2.begin) * ccw(s1.begin, s1.end, s2.end) <= 0 &&
      ccw(s2.begin, s2.end, s1.begin) * ccw(s2.begin, s2.end, s1.end) <= 0
  end
end

# require "./object/vec2"

module Geometric
  extend self

  #
  #        C [+1]
  #       /
  # A -- B
  #       \
  #        C [-1]
  #
  # A -- B -- C [+2]
  # A -- C -- B [ 0]
  # B -- A -- C [-2]
  #
  def ccw(a : Vec2, b : Vec2, c : Vec2) : Int32
    if (x = (b - a).cross(c - a).sign) != 0
      x
    elsif (b - a).dot(c - b).sign > 0
      2
    elsif (a - b).dot(c - a).sign > 0
      -2
    else
      0
    end
  end

  # Calclates the angle of `∠abc`
  def angle(a : Vec2, b : Vec2, c : Vec2)
    (c - b).rotate(-(a - b).angle).angle
  end
end
Back to top page