Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
判断一个点与已知三角形的位置关系。【输入格式】
前三行：每行一个坐标，表示该三角形的三个顶点 第四行：一个点的坐标，试判断该点与前三个点围成三角形的位置关系 (详见样例) 所有坐标值均为整数。
【输出格式】
若点在三角形内（不含边界），输出1； 若点在三角形外（不含边界），输出2； 若点在三角形边界上（不含顶点），输出3； 若点在三角形顶点上，输出4。
【数据规模】
对于100%数据，0<=所有点的横、纵坐标<=100
Sample Input1
(0,0) (3,0) (0,3) (1,1)
Sample Output1
1
【题解】
判断的优先顺序如下：
1.和顶点重合。
2.和边重合
3.在三角形内部
else
在三角形外部。
前3个种任意一个成立。后续就不再判断。直接结束程序了。
其中顶点只要和所有的点都比较一遍就可以了。
然后和边重合的情况。只要把三条边的直线方程求出来就可以了。代入看看x0,y0是否为这条边的方程的一个解，如果是一个解，则这个点在边上。直接输出在边上。
然后在三角形内部。
则这个点和三角形的三个顶点连线可以把大三角形分成3个小的三角形。
然后用海伦公式(知道3边就能求三角形面积)算出三个小三角形的面积和。
//海伦公式，设三角形的周长的一半为p，三边长为a,b,c;
//s=根号(p*(p-a)*(p-b)*(p-c));
看看这三个小的三角形的面积和与大三角形的面积是否是一样的。如果是一样的则这个点是在三角形的内部的。(如果不一样则在三角形外部！)；
因为是实数的运算。所以判断相等要用差的绝对值小于精度来判断。
【代码】
#include <cstdio>
#include <cmath>
#include <cstring>
int a[4][3],xx0,yy0;
void input_data(int &x, int &y)//输入一行坐标
{
x = 0, y = 0;
char s[500];
scanf("%s", s);
int len = strlen(s);//用strlen函数要include <cstring>这个头文件
int x1 = 0, temp;
for (int i = 1; i <= len - 1; i++)
if (s[i] != ',')
x = x * 10 + s[i] - '0';//获取x坐标
else
{
temp = i;
break;
}
for (int i = temp + 1; i <= len - 1; i++)
if (s[i] != ')')
y = y * 10 + s[i] - '0';//获取y坐标
else
break;
}
double s_triangle(double a, double b, double c) //用海伦公式来算三角形的面积。
{
double l = (a + b + c) / 2.0;
return sqrt(l*(l - a)*(l - b)*(l - c));
}
int main()
{
input_data(a[1][1], a[1][2]);//输入三个顶点的坐标
input_data(a[2][1], a[2][2]);
input_data(a[3][1], a[3][2]);
input_data(xx0, yy0);//输入要判断的点的坐标。
//在顶点上
for (int i = 1;i <= 3;i++)
if (xx0 == a[i][1] && yy0 == a[i][2])
{
printf("4");
return 0;
}
//在边上。求出三条边的直线方程。
for (int i = 2;i <= 3;i++)
for (int j = 1; j <= i - 1; j++)
{
int x1 = a[j][1], y1 = a[j][2], x2 = a[i][1], y2 = a[i][2];
//要判断的等式是这个(x-x1)/(x2-x1)==(y-y1)/(y2-y1) 也即直线方程的两点式。
if (x2 == x1)//如果这个点的横坐标相同
{
if (x2 == xx0 && ((y1 <= yy0 && yy0 <= y2) || (y2 <= yy0 && yy0 <= y1)))
{//则在边上的条件是，横坐标和xx0一样，且它们的纵坐标把yy0夹在中间
printf("3");
return 0;
}
}
else
if (y2 == y1)//如果纵坐标相同
{
if (y2 == yy0 && ((x1 <= xx0 && xx0 <= x2) || (x2 <= xx0 && xx0 <= x1)))
{//纵坐标和yy0一样，横坐标要被夹在中间
printf("3");
return 0;
}
}
else //否则的话就直接按照两点式的左右等式相同来判断是否在点上
{
double left = (xx0 - x1)*1.0 / ((x2 - x1)*1.0), right = (yy0 - y1)*1.0 / ((y2 - y1)*1.0);
double temp = right - left;//因为是实数，所以不能直接用“=”来判断
if (temp < 0)
temp = -temp;
if (temp <= 0.0001)//差的绝对值小于精度即可。
{
printf("3");
return 0;
}
}
}
//在三角形内部。用海伦公式。把三角形分成三个小的三角形。看三个小的三角形和整个大的三角形面积是否一样。
double s[5];
int num = 0;
for (int i = 2;i <= 3;i++)
for (int j = 1; j <= i - 1; j++)
{
//i和j是两个点。(xx0,yy0)充当第3个点。
double a1, b1, c1;
a1 = sqrt((a[i][1]-xx0)*(a[i][1]-xx0)+(a[i][2]-yy0)*(a[i][2]-yy0));
b1 = sqrt((a[j][1] - xx0)*(a[j][1] - xx0) + (a[j][2] - yy0)*(a[j][2] - yy0));
c1 = sqrt((a[i][1] - a[j][1])*(a[i][1] - a[j][1]) + (a[i][2] - a[j][2])*(a[i][2] - a[j][2]));
num++; //这个嵌套循环会循环3次，对应求出3个小三角形的面积。
s[num] = s_triangle(a1, b1, c1);
}
double aa1, bb1, cc1;//然后是求出大三角形的面积
aa1 = sqrt((a[1][1] - a[2][1])*(a[1][1] - a[2][1]) + (a[1][2] - a[2][2])*(a[1][2] - a[2][2]));
bb1 = sqrt((a[1][1] - a[3][1])*(a[1][1] - a[3][1]) + (a[1][2] - a[3][2])*(a[1][2] - a[3][2]));
cc1 = sqrt((a[2][1] - a[3][1])*(a[2][1] - a[3][1]) + (a[2][2] - a[3][2])*(a[2][2] - a[3][2]));
s[4] = s_triangle(aa1, bb1, cc1);
s[0] = s[1] + s[2] + s[3];//把3个三角形的面积累加起来存在s[0]
double temp1 = s[4] - s[0];//如果s[0]和s[4]相同则输出在三角形内部。
if (temp1 < 0)
temp1 = -temp1;
if (temp1 <= 0.0001)
{
printf("1");
return 0;
}
//剩下一种情况就是在三角形外部啦。
printf("2");
return 0;
}