【u027】神秘大三角

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.和顶点重合。

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;

}

巴特西