首先,判断顶点非常简单,只需要把三个点的坐标和那一个点比较即可。
我用这样的一个结构体来存储每一个点的坐标信息。
```cpp
struct vs{
int x,y;
}a[4];
```
用如下的代码就可以判断4(是不是顶点)了。
```cpp
for(i=0;i<3;i++){
if(a[i].x==a[3].x&&a[i].y==a[3].y){
printf("4\n");
return 0;
}
```
这里return 0是为了减少不必要运算,直接结束程序。
接下来,我判断3(是否在一条边上)
我的方法非常的简单粗暴,具体来说是我在0,1,2三个点里面任意取两个点,就把这两个点标记为n1,n2。
先判断n1,n2之间的向量与n1和3之间的向量是否共线。
如果不是,那3就不会在以n1和n2为端点的边上。如果共线,那么我取n1到3的长度和n2到3的长度两个里面的较大值,如果它们都小于n1到n2的长度(即较大的值小于n1到n2的长度),3就一定在n1和n2之间
用如下代码来实现它
```cpp
double l(int n1,int n2){
double l1;
int dx,dy;
dx=a[n1].x-a[n2].x;
dy=a[n1].y-a[n2].y;
l1=sqrt(dx*dx+dy*dy);
return l1;
}//这个函数可以方便地求出n1,n2之间的长度
int is3(int n1,int n2){
int dx,dy;
int xd1,yd1;
int xd2,yd2;
double l1;
dx=a[n1].x-a[n2].x;
dy=a[n1].y-a[n2].y;
xd1=a[n1].x-a[3].x;
yd1=a[n1].y-a[3].y;
xd2=a[n2].x-a[3].x;
yd2=a[n2].y-a[3].y;
if(xd1*dy!=dx*yd1)return 0;
//这里在判断两个向量是否共线
l1=sqrt(xd1*xd1+yd1*yd1);
//这是把n1和3之间的长度赋值给l1
if(sqrt(xd2*xd2+yd2*yd2)>l1)
l1=sqrt(xd2*xd2+yd2*yd2);
//如果n2和3之间的长度大于n1和3之间的长度,把l1重新赋值
if(l1>l(n1,n2))return 0;
//不符合的情况,舍去。
return 1;
}
if(is3(0,1)||is3(1,2)||is3(2,0)){
printf("3\n");
return 0;
}
//三个点阵轮流判断一遍,只要有一个满足共线的条件就可以判定为共线。
```
这样我已经把4,3两种情况都判断了一遍了,接下来要判断1,2两种情况了,其实它们是互补的,非一即二,所以可以一起来判断。
不多bb,先上代码,看看。
```
double Cos(int x1,int y1,int x2,int y2){
double l1,l2,cosa;
l1=sqrt(x1*x1+y1*y1);
l2=sqrt(x2*x2+y2*y2);
cosa=(x1*x2+y1*y2*1.0)/(l1*l2);
return cosa;
}//这个函数可以方便地求出两个向量的夹角的余弦值cos
double cosa,sina;
double cosb,sinb;
double cosc,sinc;
double cosac,sinac;
cosa=Cos(a[2].x-a[0].x,a[2].y-a[0].y,a[2].x-a[1].x,a[2].y-a[1].y);
sina=sqrt(1-cosa*cosa);
//把余弦值cos用公式算出来,正弦值sin直接根号1-cos的平方得到
cosb=Cos(a[0].x-a[2].x,a[0].y-a[2].y,a[0].x-a[1].x,a[0].y-a[1].y);
sinb=sqrt(1-cosb*cosb);
cosc=Cos(a[0].x-a[2].x,a[0].y-a[2].y,a[0].x-a[3].x,a[0].y-a[3].y);
sinc=sqrt(1-cosc*cosc);
```
![](https://cdn.luogu.com.cn/upload/image_hosting/gvpis0gx.png)
这是我的abc三个角的选取,以角021为a角,以角201为b角,以角203为c角,上面的cos值和sin值就是这三个角的。
首先,我们先判断角c是否比角b小,即角c的范围是否是0到角b。
这里要注意的是,我们不能仅仅用这三个角的sin值或cos值来判断,而是要同时把这两个值都用来判断,这是一个易被疏漏的地方。
哈哈,只要sinc和cosc都介于角2和0度的角的sin和cos值之间就可以判定角c位于0度角和角b之间了。
代码如下
```cpp
int between(double a,double b,double c){
if(a>c)swap(a,c);
if(b<a)return 0;
if(b>c)return 0;
return 1;
}
if(!(between(cosb,cosc,1)&&between(0,sinc,sinb))){
printf("2\n");
return 0;
}
```
这里判断了角c与角b的大小关系,把不符合这些条件的情况排除了(不符合这些条件的一定是位于三角形外面的)
![](https://cdn.luogu.com.cn/upload/image_hosting/0dgz13q3.png)
好了,经过了这一轮大浪淘沙一般的操作,剩下的情况只可能是角c比角b小了,我们还要判断一下,点3是否在三角形内。
我们用正弦定理,可知,如图
l1/sin(a)=l2/sin(a+b)
即l1=l2*sin()a/sin(a+b);
如果0点到3点的距离大于l1,那么3就在三角形外面。
反之,如果0点到3点的距离小于l1,那么3就在三角形里面。
代码如下
```cpp
sinac=sina*cosc+cosa*sinc;
cosac=sqrt(1-sinac*sinac);
//sinac表示角a+c的sin值,cosac同理
l1=l(0,3);
l2=l(0,2)*abs(sina/sinac);
//此处调用了上面那个求两个点之间的距离的函数
//abs一下是为了排除负值的影响(后来发现这两个sin值都是正数,不存在负值)
if(l1>l2)
printf("2\n");
else
printf("1\n");
```
大功告成辣!!!!
附上完整的代码
```cpp
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
int i;
char c[10];
struct vs{
int x,y;
}a[4];
double l(int n1,int n2);
int is3(int n1,int n2);
double cosa,sina;
double cosb,sinb;
double cosc,sinc;
double cosac,sinac;
double Cos(int x1,int y1,int x2,int y2);
int between(double a,double b,double c);
double l1,l2;
int main(){
for(i=0;i<4;i++)
scanf("(%d,%d)\n",&a[i].x,&a[i].y);
for(i=0;i<3;i++){
if(a[i].x==a[3].x&&a[i].y==a[3].y){
printf("4\n");
return 0;
}
}
if(is3(0,1)||is3(1,2)||is3(2,0)){
printf("3\n");
return 0;
}
cosa=Cos(a[2].x-a[0].x,a[2].y-a[0].y,a[2].x-a[1].x,a[2].y-a[1].y);
sina=sqrt(1-cosa*cosa);
cosb=Cos(a[0].x-a[2].x,a[0].y-a[2].y,a[0].x-a[1].x,a[0].y-a[1].y);
sinb=sqrt(1-cosb*cosb);
cosc=Cos(a[0].x-a[2].x,a[0].y-a[2].y,a[0].x-a[3].x,a[0].y-a[3].y);
sinc=sqrt(1-cosc*cosc);
if(!(between(cosb,cosc,1)&&between(0,sinc,sinb))){
printf("2\n");
return 0;
}
sinac=sina*cosc+cosa*sinc;
cosac=sqrt(1-sinac*sinac);
l1=l(0,3);
l2=l(0,2)*abs(sina/sinac);
if(l1>l2)
printf("2\n");
else
printf("1\n");
return 0;
}
double l(int n1,int n2){
double l1;
int dx,dy;
dx=a[n1].x-a[n2].x;
dy=a[n1].y-a[n2].y;
l1=sqrt(dx*dx+dy*dy);
return l1;
}
int is3(int n1,int n2){
int dx,dy;
int xd1,yd1;
int xd2,yd2;
double l1;
dx=a[n1].x-a[n2].x;
dy=a[n1].y-a[n2].y;
xd1=a[n1].x-a[3].x;
yd1=a[n1].y-a[3].y;
xd2=a[n2].x-a[3].x;
yd2=a[n2].y-a[3].y;
if(xd1*dy!=dx*yd1)return 0;
l1=sqrt(xd1*xd1+yd1*yd1);
if(sqrt(xd2*xd2+yd2*yd2)>l1)
l1=sqrt(xd2*xd2+yd2*yd2);
if(l1>l(n1,n2))return 0;
return 1;
}
double Cos(int x1,int y1,int x2,int y2){
double l1,l2,cosa;
l1=sqrt(x1*x1+y1*y1);
l2=sqrt(x2*x2+y2*y2);
cosa=(x1*x2+y1*y2*1.0)/(l1*l2);
return cosa;
}
int between(double a,double b,double c){
if(a>c)swap(a,c);
if(b<a)return 0;
if(b>c)return 0;
return 1;
}
```
by sdykyh @ 2021-07-20 20:27:21
@[巴菲特](/user/171851)
我似乎也遇到了同样的问题,有一个检查点总是不通过
后来发现自己的代码的问题了。我是通过三个点组成的三角形面积是否为0来判断三点是否共线的。这样可能有一种情况,就是点D在三角形外面,但是被三角形一边所在的直线经过。这种情况会导致判断错误。
不知道提问者是否也是这种情况
by OhanaTyan @ 2022-04-13 21:24:12