アルゴリズムと数学 098

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bu

内部の点なら、その点と各辺からなる角度の和が2πや-2πになるはずです。外部の点なら0になります。なお、角度は符号を考えます。これは外積を使うと計算できます。

// Polygon and Point
#![allow(non_snake_case)]

use std::ops::{Add, Sub};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

#[derive(Clone, Copy)]
#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i64,
    y: i64,
}

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Point {
    fn new(x: i64, y: i64) -> Point {
        Point { x, y }
    }
    
    fn inner_product(v1: &Point, v2: &Point) -> i64 {
        v1.x * v2.x + v1.y * v2.y
    }
    
    fn outer_product(v1: &Point, v2: &Point) -> i64 {
        v1.x * v2.y - v1.y * v2.x
    }
    
    fn len(&self) -> f64 {
        (Point::inner_product(self, self) as f64).sqrt()
    }
    
    fn angle(pt1: &Point, pt2: &Point, pt3: &Point) -> f64 {
        let v1 = *pt1 - *pt2;
        let v2 = *pt3 - *pt2;
        let x = (Point::inner_product(&v1, &v2) as f64) / (v1.len() * v2.len());
        let y = if x < -1.0 {
            std::f64::consts::PI
        }
        else if x > 1.0 {
            0.0
        }
        else {
            x.acos()
        };
        if Point::outer_product(&v1, &v2) >= 0 {
            y
        }
        else {
            -y
        }
    }
    
    fn read() -> Point {
        let v: Vec<i64> = read_vec();
        Point::new(v[0], v[1])
    }
}


//////////////////// process ////////////////////

fn read_input() -> (Vec<Point>, Point) {
    let N: usize = read();
    let polygon: Vec<Point> = (0..N).map(|_| Point::read()).collect();
    let point = Point::read();
    (polygon, point)
}

fn edges(polygon: &Vec<Point>) -> Vec<(Point, Point)> {
    let L = polygon.len();
    (0..L).map(|i| (polygon[i], polygon[(i+1)%L])).
                        collect::<Vec<(Point, Point)>>()
}

fn f(polygon: Vec<Point>, point: Point) -> bool {
    let s = edges(&polygon).into_iter().
            map(|(pt1, pt2)| Point::angle(&pt1, &point, &pt2)).sum::<f64>();
    -0.1 < s && s < 0.1
}

fn main() {
    let (polygon, point) = read_input();
    let is_outside = f(polygon, point);
    println!("{}", if is_outside { "OUTSIDE" } else { "INSIDE" })
}