鸽者文明的三体问题（数学）

本文主要是介绍鸽者文明的三体问题（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：题目的太概意思就是给你很多个三角形区域，平面中的点满足在一个三角形区域就被覆盖了一次，如果覆盖了奇数次就存在引力，否则不存在。
那么这道题的关键就是去判断点（xqi，yqi）是否在三角形区域内。

在这里插入图片描述

判断p点是否在三角形内部：
用面积法去判定
如果在三角形内部就必须满足 SABC = S ABP + SACP+SBCP;

因为这道题目给出的是三个点的坐标
那么三角形的面积就用向量叉乘/2来计算。

ABC的面积 = 向量AC叉乘向量AB;

#include <bits/stdc++.h>
using namespace std;
struct node{int x,y;
};
node a[10010][3];
double area(node A,node B,node C){double x1 = B.x - A.x;double x2 = C.x - A.x;double y1 = B.y - A.y;double y2 = C.y - A.y;return abs(x1*y2-x2*y1)/2.0;
}
int main()
{ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);int n,q; cin>>n>>q;for(int i=0;i<n;i++){for(int j=0;j<3;j++){cin>>a[i][j].x>>a[i][j].y;}}while(q--){node xx; cin>>xx.x>>xx.y;int ans = 0;for(int i=0;i<n;i++){double area1 = area(a[i][0],a[i][1],a[i][2]);double area2 = area(a[i][0],a[i][1],xx)+area(a[i][0],a[i][2],xx)+area(a[i][1],a[i][2],xx);if(area1==area2) ans++;}if(ans%2==0) cout<<"No"<<endl;else cout<<"Yes"<<endl;}return 0;
}