核心内容摘要
绿猫舍：守护猫咪的幸福，雕琢每一个毛茸茸的梦想
题目描述判断一个点与已知三角形的位置关系。
输入格式前三行每行一个坐标表示该三角形的三个顶点。
第四行一个点的坐标试判断该点与前三个点围成三角形的位置关系。
所有坐标值均为整数。
输出格式若点在三角形内不含边界输出 1若点在三角形外不含边界输出 2若点在三角形边界上不含顶点输出 3若点在三角形顶点上输出 4。
输入输出样例输入 #1复制运行(0,
(3,
(0,
(1,
输出 #1复制运行1说明/提示数据规模与约定对于 100% 数据0≤xi,yi≤100。
问题背景在计算几何中判断一个点P与已知三角形ABC的位置关系是一个非常基础但容易出错的问题。
我们需要区分以下四种情况点在三角形顶点上。
点在三角形边界上不含顶点。
点在三角形内部。
点在三角形外部。
如果不小心处理很容易掉进“点在边的延长线上”或者“浮点数精度丢失”的陷阱中。
本文将介绍一种利用叉积面积法的稳健解决方案。
核心算法面积法相比于计算夹角之和或射线法面积法在处理整数坐标时具有天然优势全程无浮点运算无精度误差。
原理三角形的面积可以通过向量叉积计算我们在代码中为了避免除以2产生小数直接计算2倍面积即叉积的绝对值。
设大三角形面积为点P与三个顶点形成的三个小三角形面积分别为。
判定逻辑顶点判定直接比较坐标是否相等。
位置判定计算面积和。
在外部面积溢出。
在内部或边上面积守恒。
边界与延长线的区分如果某个小三角形面积为 0例如说明P在直线AB上。
此时必须结合面积守恒判定若在边上。
若在延长线上即外部。
代码实现细节输入技巧题目输入格式为(x,y)利用scanf( (%d,%d), ...)中的空格跳过所有空白符格式化读取十分方便。
向量构造无需构造全部向量利用 helper 函数即时计算。
数据类型题目坐标范围面积最大约int足够无需long long。
完整代码//叉积判断 #include iostream #include cmath//对应abs函数 using namespace std; typedef pairint,int pii; pii n[5]; int cross(pii a,pii b){//计算a b叉积 return (a.first*b.second-a.second*b.first); } pii product(int a,int b){//计算a-b向量坐标 int xn[b].first-n[a].first; int yn[b].second-n[a].second; return {x,y}; } int main(){ //n1 n2 n3存三角形三个点n4是需要判断的点 for(int i1;i4;i){ //格式串前的空格非常关键用于跳过换行符和空格 scanf( (%d,%d),n[i].first,n[i].second); } pii n14,n24,n34,n21,n12,n13;//1 2 3点分别与4点相连所构成的向量 //n14表示向量P1-P4(即顶点1到点P) n14product(1,
; n24product(2,
; n34product(3,
; n21product(2,
; n12product(1,
; n13product(1,
; //若点在三角形顶点上输出4 if((n
first0n
second
||(n
first0n
second
||(n
first0n
second
){ cout4; return 0; } //不在顶点上就判断该点是在内部还是外部还是边上 //如果在内部三个顶点与该点构成的三个小三角面积应该等于三个顶点构成的三角形面积 //如果在外部三个顶点与该点构成的三个小三角面积大于三个顶点构成的三角形面积 //如果在边上三个顶点与该点构成的三个小三角面积有一个等于0这里容易出问题如果在三角形外部但是在边的延长线上其实也会有个小三角形面积为0 int sumabs(cross(n12,n
);//三个顶点构成的三角形面积的二倍。
不除以2避免精度问题 //sum1 2 3是三角形三个顶点中两两一组与题目给出端点构成三角形面积的二倍 int sum1abs(cross(n14,n
); int sum2abs(cross(n24,n
); int sum3abs(cross(n34,n
); //端点在边上一定有一个三角形面积为0接下来还要去判断三个小三角面积之和是否等于三个顶点构成的三角形面积之和等于就在边上大于就在延长线上(外部) if(sum10 || sum20 || sum
{ if(sumsum1sum2sum
{ cout3; return 0; } else{ cout2; return 0; } } else if(sumsum1sum2sum
{//端点在内部大三角形面积一定等于三个小三角形面积之和 cout1; return 0; } else{//端点在外部三个小三角形面积之和一定大于三个顶点构成三角形面积 cout2; return 0; } }
5.
总结解决计算几何问题的关键在于“把几何关系转化为代数关系”。
与其纠结复杂的角度判断不如使用面积法。
与其纠结浮点数的误差不如全程使用整数运算。
通过sumsum1sum2sum3这一条核心公式我们就能完美地将“内部/边上”与“外部/延长线”区分开来。