在二维坐标系中,所有的值都是double类型,那么一个三角形可以由3个点来代表,给定3个点代表的三角形,再给定一个点(x, y),判断(x, y)是否在三角形中
输入有四行,每行两个浮点数。
前三行的6个数分别代表三角形的三个顶点的坐标
最后两个数分别表示(x, y)
若(x, y)在三角形中,输出"Yes"
否则输出"No"
-1.00 0.00 1.50 3.50 2.73 -3.12 1.23 0.23
Yes
样例中的图形大致如下
-1.00 0.00 1.50 3.50 2.73 -3.12 2333.33 233333.33
No
#include <bits/stdc++.h> using namespace std; struct P{ double x,y; }; double F(P a, P b){ return acos((a.x*b.x+a.y*b.y)/(sqrt(a.x*a.x+a.y*a.y)*sqrt(b.x*b.x+b.y*b.y))); } int main(){ P p[4], d[3]; for(int i=0;i<4;i++) cin>>p[i].x>>p[i].y; for(int i=0;i<3;i++){ d[i].x = p[i].x - p[3].x; d[i].y = p[i].y - p[3].y; } double a = F(d[0], d[1]); double b = F(d[1], d[2]); double c = F(d[2], d[0]); if(abs((a+b+c) - 2*acos(-1)) < 1e-6) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
#include<iostream> using namespace std; struct point { public: double x, y; point& operator-(point& q) { point* p = new point(); p->x = x - q.x; p->y = y - q.y; return *p; } }; double crossZ(point p, point q) { return p.x * q.y - p.y * q.x; } int main() { point p, a, b, c; cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y; cin >> p.x >> p.y; point la = b - a, lb = c - b, lc = a - c; int j = crossZ(p - a, la), k = crossZ(p - b, lb), l = crossZ(p - c, lc); if ((l > 0 && j > 0 && k > 0) || (l < 0 && j < 0 && k < 0)) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
#include <iostream> #include <cmath> using namespace std; struct Point { double x; double y; Point(double x = 0.0, double y = 0.0) : x(x), y(y) {} }; bool IsAntiClockwise(const Point& p1, const Point& p2, const Point& p3) { // 利用叉乘判断 如果p1 p2 p3 三个是逆时针顺序 // 即p3在p1 p2右侧 那么 p1p2 × p1p3 > 0 // a × b = axby - aybx // p1p2 = (p2.x - p1.x, p2.y - p1.y) // p1p3 = (p3.x - p1.x, p3.y - p1.y) return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) > 0; } bool inTriangle(const Point& p1, const Point& p2, const Point& p3, const Point& o) { // 确保p1 p2 p3 是一个逆时针顺序 if (!IsAntiClockwise(p1, p2, p3)) return inTriangle(p1, p3, p2, o); return IsAntiClockwise(p1, p2, o) && IsAntiClockwise(o, p2, p3) && IsAntiClockwise(o, p3, p1); } int main() { Point p1, p2, p3, o; // cout << "plz enter point p1 as x y : "; cin >> p1.x >> p1.y; // cout << "plz enter point p2 as x y : "; cin >> p2.x >> p2.y; // cout << "plz enter point p3 as x y : "; cin >> p3.x >> p3.y; // cout << "plz enter point o as x y : "; cin >> o.x >> o.y; if (inTriangle(p1, p2, p3, o)) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; int i = 0; // 三角形三个顶点的坐标以及待判断点的坐标 double[] x = new double[4]; double[] y = new double[4]; while((line = br.readLine()) != null){ String[] params = line.trim().split(" "); x[i] = Double.parseDouble(params[0]); y[i] = Double.parseDouble(params[1]); i ++; } // 看待检测点是否在三角形三条边的同一方向即可 int res = Math.abs(crossProduct(x[0], y[0], x[1], y[1], x[3], y[3]) + crossProduct(x[1], y[1], x[2], y[2], x[3], y[3]) + crossProduct(x[2], y[2], x[0], y[0], x[3], y[3])); if(res == 3) System.out.println("Yes"); else System.out.println("No"); } private static int crossProduct(double x1, double y1, double x2, double y2, double x, double y) { x2 -= x1; y2 -= y1; x -= x1; y -= y1; double crossRes = x * y2 - x2 * y; if(crossRes > 0) return 1; else if(crossRes < 0) return -1; else return 0; } }这里说明一下为什么通过向量a=(x2-x1,y2-y1)和b=(x-x1,y-y1)叉积的符号可以判断点(x,y)与向量(x2-x1,y2-y1)的位置关系。
#include <iostream> using namespace std; struct node { double x, y; double operator ^(node b) { return x * b.y - y * b.x; } node operator - (node b) { node ans; ans.x = x - b.x; ans.y = y - b.y; return ans; } }a[7]; int main() { node Temp; for (int i = 1;i <= 3;i++) { cin >> a[i].x >> a[i].y; } cin >> Temp.x >> Temp.y; node ab = a[2] - a[1]; node bc = a[3] - a[2]; node ba = a[1] - a[3]; node aT = a[1] - Temp; node bT = a[2] - Temp; node cT = a[3] - Temp; double one = ab ^ aT; double two = bc ^ bT; double three = ba ^ cT; if ( (one > 0 && two > 0 && three > 0) || (one < 0 && two < 0 && three < 0)) { cout << "Yes" << endl; } else { cout << "No" << endl; } }
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(()) }
算法导论——计算几何学一章提到,使用向量外积的正负性,判断点和向量之间的位置关系
#include <bits/stdc++.h> using namespace std; int direction(double x1, double y1, double x2, double y2, double x3, double y3){ /* 求向量V和点(x3, y3)之间的位置关系,(x1, y1)是V的起点,(x2, y2)是V的终点 */ //得到向量V x2 -= x1; y2 -= y1; //V的起点(x1, y1)与目标点(x3, y3)构成新的向量U x3 -= x1; y3 -= y1; double res = x3 * y2 - x2 * y3;//求两向量U和V的外积(叉积) if(res < 0) return -1;//<0在逆时针方向 if(res == 0) return 0;//=0共线 if(res > 0) return 1;//>0说明点在向量顺时针方向 } int main(){ double x1, y1; double x2, y2; double x3, y3; cin >> x1 >> y1; cin >> x2 >> y2; cin >> x3 >> y3; double x4, y4; cin >> x4 >> y4; //(x1, y1)与(x2, y2)构成向量V1 //(x2, y2)与(x3, y3)构成向量V2 //(x3, y3)与(x1, y1)构成向量V3 int res1 = direction(x1, y1, x2, y2, x4, y4); int res2 = direction(x2, y2, x3, y4, x4, y4); int res3 = direction(x3, y3, x1, y1, x4, y4); if(abs(res1 + res2 + res3) == 3){//全-1或全1,表示点(x4, y4)同时在三个向量的同一侧 cout << "Yes"; }else { cout << "No"; } return 0; }