P7934 题解

Jerrlee✅ · 2021-11-10 17:02:49 · 题解

题意

给出一个三角形三个顶点的坐标以及 n 个点 p 的坐标，求这个三角形的面积和在这 n 个点中，有多少个点在这个三角形内部及边界上。

思路

三角形面积的公式已经给出了：\dfrac{|x_a(y_b-y_c)+x_b(y_c-y_a)+x_c(y_a-y_b)|}2，所以我们只需要找到一种方法来检查输入的点 p 是否在三角形 ABC 内。

有一种方法可以满足题意，就是只计算三角形的面积。更准确地说，当且只有 p 在 ABC 内时，三角形 ABP、ACP 和 BCP 的面积之和等于 ABC 的面积。

代码

#include<cstdio>
struct pt{
    int x,y; //定义点的坐标结构体
};
int area(pt a,pt b,pt c){ //计算面积
   int t=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
   if(t<0) return -t; //面积非负
   else return t;
}
int main(){
   pt a,b,c;
   scanf("%d%d%d%d%d%d",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
   int n,ans=0;
   scanf("%d",&n);
   for(int i=0;i<n;i++){
      pt p;
      scanf("%d%d",&p.x,&p.y);
      if(area(a,b,p)+area(a,c,p)+area(b,c,p)==area(a,b,c)) ans++; //判断面积是否相等
   }
   printf("%.1lf\n%d\n",area(a,b,c)/2.0,ans); //代入公式
}

AC记录