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" }) }