#[macro_use]

extern crate fpnum;

use fpnum::{distance, FPNum, FPPoint};

use std::{

    cmp::{max, min},

    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Range, RangeInclusive, Sub, SubAssign},

};

#[derive(PartialEq, Eq, Clone, Copy, Debug)]

pub struct Point {

    pub x: i32,

    pub y: i32,

}

impl Point {

    #[inline]

    pub fn new(x: i32, y: i32) -> Self {

        Self { x, y }

    }

    #[inline]

    pub fn diag(v: i32) -> Self {

        Self::new(v, v)

    }

    #[inline]

    pub fn zero() -> Self {

        Self::new(0, 0)

    }

    #[inline]

    pub fn signum(self) -> Self {

        Self::new(self.x.signum(), self.y.signum())

    }

    #[inline]

    pub fn abs(self) -> Self {

        Self::new(self.x.abs(), self.y.abs())

    }

    #[inline]

    pub fn dot(self, other: Point) -> i32 {

        self.x * other.x + self.y * other.y

    }

    #[inline]

    pub fn max_norm(self) -> i32 {

        std::cmp::max(self.x.abs(), self.y.abs())

    }

    #[inline]

    pub fn integral_norm(self) -> u32 {

        distance(self.x, self.y).abs_round()

    }

    #[inline]

    pub fn transform(self, matrix: &[i32; 4]) -> Self {

        Point::new(

            matrix[0] * self.x + matrix[1] * self.y,

            matrix[2] * self.x + matrix[3] * self.y,

        )

    }

    #[inline]

    pub fn rotate90(self) -> Self {

        Point::new(self.y, -self.x)

    }

    #[inline]

    pub fn cross(self, other: Point) -> i32 {

        self.dot(other.rotate90())

    }

    #[inline]

    pub fn clamp(self, rect: &Rect) -> Point {

        Point::new(rect.x_range().clamp(self.x), rect.y_range().clamp(self.y))

    }

    #[inline]

    pub fn line_to(self, end: Point) -> Line {

        Line::new(self, end)

    }

    #[inline]

    pub fn ray_with_dir(self, direction: Point) -> Ray {

        Ray::new(self, direction)

    }

    #[inline]

    pub fn tangent_mul(self, x: i32) -> i32 {

        x * self.y / self.x

    }

    #[inline]

    pub fn cotangent_mul(self, y: i32) -> i32 {

        y * self.x / self.y

    }

    #[inline]

    pub fn to_fppoint(self) -> FPPoint {

        FPPoint::new(self.x.into(), self.y.into())

    }

    #[inline]

    pub fn from_fppoint(p: &FPPoint) -> Self {

        Self::new(p.x().round(), p.y().round())

    }

}

#[derive(PartialEq, Eq, Clone, Copy, Debug)]

pub struct Size {

    pub width: usize,

    pub height: usize,

}

impl Size {

    #[inline]

    pub fn new(width: usize, height: usize) -> Self {

        Size { width, height }

    }

    #[inline]

    pub fn square(size: usize) -> Self {

        Size {

            width: size,

            height: size,

        }

    }

    #[inline]

    pub fn area(&self) -> usize {

        self.width * self.height

    }

    #[inline]

    pub fn linear_index(&self, x: usize, y: usize) -> usize {

        y * self.width + x

    }

    #[inline]

    pub fn is_power_of_two(&self) -> bool {

        self.width.is_power_of_two() && self.height.is_power_of_two()

    }

    #[inline]

    pub fn next_power_of_two(&self) -> Self {

        Self {

            width: self.width.next_power_of_two(),

            height: self.height.next_power_of_two(),

        }

    }

    #[inline]

    pub fn to_mask(&self) -> SizeMask {

        SizeMask::new(*self)

    }

    #[inline]

    pub fn to_square(&self) -> Size {

        Size::square(max(self.width, self.height))

    }

    pub fn to_grid_index(&self) -> GridIndex {

        GridIndex::new(*self)

    }

}

pub struct SizeMask {

    size: Size,

}

impl SizeMask {

    #[inline]

    pub fn new(size: Size) -> Self {

        assert!(size.is_power_of_two());

        let size = Size {

            width: !(size.width - 1),

            height: !(size.height - 1),

        };

        Self { size }

    }

    #[inline]

    pub fn contains_x<T: Into<usize>>(&self, x: T) -> bool {

        (self.size.width & x.into()) == 0

    }

    #[inline]

    pub fn contains_y<T: Into<usize>>(&self, y: T) -> bool {

        (self.size.height & y.into()) == 0

    }

    #[inline]

    pub fn contains(&self, point: Point) -> bool {

        self.contains_x(point.x as usize) && self.contains_y(point.y as usize)

    }

}

pub struct GridIndex {

    shift: Point,

}

impl GridIndex {

    pub fn new(size: Size) -> Self {

        assert!(size.is_power_of_two());

        let shift = Point::new(

            size.width.trailing_zeros() as i32,

            size.height.trailing_zeros() as i32,

        );

        Self { shift }

    }

    pub fn map(&self, position: Point) -> Point {

        Point::new(position.x >> self.shift.x, position.y >> self.shift.y)

    }

}

macro_rules! bin_op_impl {

    ($op: ty, $name: tt) => {

        impl $op for Point {

            type Output = Self;

            #[inline]

            fn $name(self, rhs: Self) -> Self::Output {

                Self::new(self.x.$name(rhs.x), self.y.$name(rhs.y))

            }

        }

    };

}

macro_rules! scalar_bin_op_impl {

    ($($op: tt)::+, $name: tt) => {

        impl $($op)::+<i32> for Point {

            type Output = Self;

            #[inline]

            fn $name(self, rhs: i32) -> Self::Output {

                Self::new(self.x.$name(rhs), self.y.$name(rhs))

            }

        }

    };

}

macro_rules! bin_assign_op_impl {

    ($op: ty, $name: tt) => {

        impl $op for Point {

            #[inline]

            fn $name(&mut self, rhs: Self) {

                self.x.$name(rhs.x);

                self.y.$name(rhs.y);

            }

        }

    };

}

bin_op_impl!(Add, add);

bin_op_impl!(Sub, sub);

bin_op_impl!(Mul, mul);

bin_op_impl!(Div, div);

scalar_bin_op_impl!(Mul, mul);

scalar_bin_op_impl!(Div, div);

bin_assign_op_impl!(AddAssign, add_assign);

bin_assign_op_impl!(SubAssign, sub_assign);

bin_assign_op_impl!(MulAssign, mul_assign);

bin_assign_op_impl!(DivAssign, div_assign);

#[derive(PartialEq, Eq, Clone, Copy, Debug)]

pub struct Rect {

    top_left: Point,

    bottom_right: Point,

}

impl Rect {

    #[inline]

    pub fn new(top_left: Point, bottom_right: Point) -> Self {

        assert!(top_left.x <= bottom_right.x + 1);

        assert!(top_left.y <= bottom_right.y + 1);

        Self {

            top_left,

            bottom_right,

        }

    }

    pub fn from_box(left: i32, right: i32, top: i32, bottom: i32) -> Self {

        Self::new(Point::new(left, top), Point::new(right, bottom))

    }

    pub fn from_size(top_left: Point, size: Size) -> Self {

        Self::new(

            top_left,

            top_left + Point::new(size.width as i32 - 1, size.height as i32 - 1),

        )

    }

    pub fn from_size_coords(x: i32, y: i32, width: usize, height: usize) -> Self {

        Self::from_size(Point::new(x, y), Size::new(width, height))

    }

    pub fn at_origin(size: Size) -> Self {

        Self::from_size(Point::zero(), size)

    }

    #[inline]

    pub fn width(&self) -> usize {

        (self.right() - self.left() + 1) as usize

    }

    #[inline]

    pub fn height(&self) -> usize {

        (self.right() - self.left() + 1) as usize

    }

    #[inline]

    pub fn size(&self) -> Size {

        Size::new(self.width(), self.height())

    }

    #[inline]

    pub fn area(&self) -> usize {

        self.size().area()

    }

    #[inline]

    pub fn left(&self) -> i32 {

        self.top_left().x

    }

    #[inline]

    pub fn top(&self) -> i32 {

        self.top_left().y

    }

    #[inline]

    pub fn right(&self) -> i32 {

        self.bottom_right().x

    }

    #[inline]

    pub fn bottom(&self) -> i32 {

        self.bottom_right().y

    }

    #[inline]

    pub fn top_left(&self) -> Point {

        self.top_left

    }

    #[inline]

    pub fn bottom_right(&self) -> Point {

        self.bottom_right

    }

    #[inline]

    pub fn center(&self) -> Point {

        (self.top_left() + self.bottom_right()) / 2

    }

    #[inline]

    pub fn with_margin(&self, margin: i32) -> Self {

        let offset = Point::diag(margin);

        Self::new(self.top_left() + offset, self.bottom_right() - offset)

    }

    #[inline]

    pub fn x_range(&self) -> RangeInclusive<i32> {

        self.left()..=self.right()

    }

    #[inline]

    pub fn y_range(&self) -> RangeInclusive<i32> {

        self.top()..=self.bottom()

    }

    #[inline]

    pub fn contains(&self, point: Point) -> bool {

        self.x_range().contains(point.x) && self.y_range().contains(point.y)

    }

    #[inline]

    pub fn contains_inside(&self, point: Point) -> bool {

        point.x > self.left()

            && point.x < self.right()

            && point.y > self.top()

            && point.y < self.bottom()

    }

    #[inline]

    pub fn intersects(&self, other: &Rect) -> bool {

        self.left() <= self.right()

            && self.right() >= other.left()

            && self.top() <= other.bottom()

            && self.bottom() >= other.top()

    }

    #[inline]

    pub fn split_at(&self, point: Point) -> [Rect; 4] {

        assert!(self.contains_inside(point));

        [

            Self::from_box(self.left(), point.x, self.top(), point.y),

            Self::from_box(point.x, self.right(), self.top(), point.y),

            Self::from_box(point.x, self.right(), point.y, self.bottom()),

            Self::from_box(self.left(), point.x, point.y, self.bottom()),

        ]

    }

    #[inline]

    pub fn quotient(self, x: usize, y: usize) -> Point {

        self.top_left() + Point::new((x % self.width()) as i32, (y % self.height()) as i32)

    }

}

trait RangeContains<T> {

    fn contains(&self, value: T) -> bool;

}

impl<T: Ord> RangeContains<T> for Range<T> {

    fn contains(&self, value: T) -> bool {

        value >= self.start && value < self.end

    }

}

impl<T: Ord> RangeContains<T> for RangeInclusive<T> {

    fn contains(&self, value: T) -> bool {

        value >= *self.start() && value <= *self.end()

    }

}

trait RangeClamp<T> {

    fn clamp(&self, value: T) -> T;

}

impl<T: Ord + Copy> RangeClamp<T> for RangeInclusive<T> {

    fn clamp(&self, value: T) -> T {

        if value < *self.start() {

            *self.start()

        } else if value > *self.end() {

            *self.end()

        } else {

            value

        }

    }

}

pub struct Polygon {

    vertices: Vec<Point>,

}

impl Polygon {

    pub fn new(vertices: &[Point]) -> Self {

        let mut v = Vec::with_capacity(vertices.len() + 1);

        v.extend_from_slice(vertices);

        if !v.is_empty() {

            let start = v[0];

            v.push(start);

        }

        Self { vertices: v }