神秘大三角（洛谷P1355）-编程实验室

题目描述

判断一个点与已知三角形的位置关系。

输入格式

前三行，每行一个坐标，表示该三角形的三个顶点。

第四行，一个点的坐标，试判断该点与前三个点围成三角形的位置关系。

所有坐标值均为整数。

输出格式

若点在三角形内（不含边界），输出 1；
若点在三角形外（不含边界），输出 2；
若点在三角形边界上（不含顶点），输出 3；
若点在三角形顶点上，输出 4。

输入输出样例

输入 #1复制运行

(0,0) (3,0) (0,3) (1,1)

输出 #1复制运行

说明/提示

数据规模与约定

对于 100% 数据，0≤xi,yi≤100。

1. 问题背景

在计算几何中，判断一个点P与已知三角形ABC的位置关系是一个非常基础但容易出错的问题。我们需要区分以下四种情况：

点在三角形顶点上。
点在三角形边界上（不含顶点）。
点在三角形内部。
点在三角形外部。

如果不小心处理，很容易掉进“点在边的延长线上”或者“浮点数精度丢失”的陷阱中。本文将介绍一种利用叉积（面积法）的稳健解决方案。

2. 核心算法：面积法

相比于计算夹角之和或射线法，面积法在处理整数坐标时具有天然优势：全程无浮点运算，无精度误差。

原理

三角形的面积可以通过向量叉积计算：

我们在代码中为了避免除以2产生小数，直接计算2倍面积（即叉积的绝对值）。

设大三角形面积为，点P与三个顶点形成的三个小三角形面积分别为。

判定逻辑

顶点判定：直接比较坐标是否相等。
位置判定：
- 计算面积和：。
- 在外部：（面积溢出）。
- 在内部或边上：（面积守恒）。
边界与延长线的区分：
- 如果某个小三角形面积为 0（例如），说明P在直线AB上。
- 此时必须结合面积守恒判定：
  - 若在边上。
  - 若在延长线上（即外部）。

3. 代码实现细节

输入技巧：题目输入格式为(x,y)，利用scanf(" (%d,%d)", ...)中的空格跳过所有空白符，格式化读取十分方便。
向量构造：无需构造全部向量，利用 helper 函数即时计算。
数据类型：题目坐标范围，面积最大约，int足够，无需long long。

4. 完整代码

//叉积判断 #include <iostream> #include <cmath>//对应abs函数 using namespace std; typedef pair<int,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 x=n[b].first-n[a].first; int y=n[b].second-n[a].second; return {x,y}; } int main(){ //n1 n2 n3存三角形三个点，n4是需要判断的点 for(int i=1;i<=4;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) n14=product(1,4); n24=product(2,4); n34=product(3,4); n21=product(2,1); n12=product(1,2); n13=product(1,3); //若点在三角形顶点上，输出4 if((n14.first==0&&n14.second==0)||(n24.first==0&&n24.second==0) ||(n34.first==0&&n34.second==0)){ cout<<4; return 0; } //不在顶点上，就判断该点是在内部还是外部还是边上 //如果在内部，三个顶点与该点构成的三个小三角面积应该等于三个顶点构成的三角形面积 //如果在外部，三个顶点与该点构成的三个小三角面积大于三个顶点构成的三角形面积 //如果在边上，三个顶点与该点构成的三个小三角面积有一个等于0（这里容易出问题）如果在三角形外部但是在边的延长线上其实也会有个小三角形面积为0 int sum=abs(cross(n12,n13));//三个顶点构成的三角形面积的二倍。不除以2避免精度问题 //sum1 2 3是三角形三个顶点中两两一组与题目给出端点构成三角形面积的二倍 int sum1=abs(cross(n14,n24)); int sum2=abs(cross(n24,n34)); int sum3=abs(cross(n34,n14)); //端点在边上，一定有一个三角形面积为0，接下来还要去判断三个小三角面积之和是否等于三个顶点构成的三角形面积之和，等于就在边上，大于就在延长线上(外部) if(sum1==0 || sum2==0 || sum3==0){ if(sum==sum1+sum2+sum3){ cout<<3; return 0; } else{ cout<<2; return 0; } } else if(sum==sum1+sum2+sum3){//端点在内部，大三角形面积一定等于三个小三角形面积之和 cout<<1; return 0; } else{//端点在外部，三个小三角形面积之和一定大于三个顶点构成三角形面积 cout<<2; return 0; } }