判断一个点是否在三角形内部

[编程题]判断一个点是否在三角形内部

热度指数：1703 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在二维坐标系中，所有的值都是double类型，那么一个三角形可以由3个点来代表，给定3个点代表的三角形，再给定一个点(x, y)，判断(x, y)是否在三角形中

输入描述:

输入有四行，每行两个浮点数。

前三行的6个数分别代表三角形的三个顶点的坐标

最后两个数分别表示(x, y)

输出描述:

若(x, y)在三角形中，输出"Yes"

否则输出"No"

示例1

输入

-1.00 0.00
1.50 3.50
2.73 -3.12
1.23 0.23

输出

Yes

说明

样例中的图形大致如下

示例2

输入

-1.00 0.00
1.50 3.50
2.73 -3.12
2333.33 233333.33

输出

No

备注:

算法知识视频讲解

Rust

AlexanderGan

use std::io::{prelude::*, BufReader};

pub fn main() {
    let mut triangle_and_point: Vec<Vec<f32>> = vec![];
    read_triangle_and_point(&mut triangle_and_point);
    
    let point_a = (triangle_and_point[0][0], triangle_and_point[0][1]);
    let point_b = (triangle_and_point[1][0], triangle_and_point[1][1]);
    let point_c = (triangle_and_point[2][0], triangle_and_point[2][1]);
    let point = (triangle_and_point[3][0], triangle_and_point[3][1]);
    
    let vec_ab = (point_b.0 - point_a.0, point_b.1 - point_a.1);
    let vec_bc = (point_c.0 - point_b.0, point_c.1 - point_b.1);
    let vec_ca = (point_a.0 - point_c.0, point_a.1 - point_c.1);
    
    let ans = 
        is_ipsilateral(vec_ab, 
            (point.0 - point_a.0, point.1 - point_a.1), 
            (point_c.0 - point_a.0, point_c.1 - point_a.1)) &&
        is_ipsilateral(vec_bc, 
            (point.0 - point_b.0, point.1 - point_b.1), 
            (point_a.0 - point_b.0, point_a.1 - point_b.1)) &&
        is_ipsilateral(vec_ca, 
            (point.0 - point_c.0, point.1 - point_c.1), 
            (point_b.0 - point_c.0, point_b.1 - point_c.1));
    
    if ans {
        println!("Yes");
    } else {
        println!("No");
    }
}

//判断是否同侧
fn is_ipsilateral(vec_main: (f32, f32), vec1: (f32, f32), vec2: (f32, f32)) -> bool {
    let sign_a = if vec_main.0 * vec1.1 - vec1.0 * vec_main.1 > 0.0 {true} else {false};
    let sign_b = if vec_main.0 * vec2.1 - vec2.0 * vec_main.1 > 0.0 {true} else {false};
    return sign_a == sign_b;
}

fn read_triangle_and_point(triangle_and_point: &mut Vec<Vec<f32>>) -> Result<(), std::io::Error> {
    let stdin = std::io::stdin();
    let handle = stdin.lock();//手动上锁，避免每次读取加锁的开销
    let mut reader = BufReader::new(handle);//使用带缓冲的读取
    let mut v1_tmp: Vec<f32>;

    for _ in 0..4 {
        let mut tmp_str = String::new();
        reader.read_line(&mut tmp_str).expect("read matrix error!");
        v1_tmp = tmp_str.trim().split(' ').map(|x| x.parse::<f32>().unwrap()).collect();
        triangle_and_point.push(v1_tmp);
    }

    Ok(())
}

发表于 2022-03-23 14:54:31 回复(1)