UVA143题解

wuwendongxi · 2021-08-21 12:36:11 · 题解

题意：

给定三角形的顶点坐标，求有多少个点在三角形内或在三角形的边上。

题解：

• 首先观察数据范围坐标在 100 以内，想到暴力判断每个点是否在三角形中。

• 如何判断点是否在三角形中？

• 上面的图讲的非常清楚了，如何求三角形的面积？

解决这个问题前，你需要学习向量叉积。

事实上，向量 \overrightarrow{a}\times \overrightarrow{b} 为 \overrightarrow{a}，\overrightarrow{b} 构成的平行四边形面积，即三角形面积的两倍。

• 最后，叉积计算公式：\left| \overrightarrow{a}\times \overrightarrow{b}\right| =X_{a}Y_{b}-Y_{a}X_{b}

• 最后的最后，如果你提交始终无法通过，对拍后又找不到错误，请检查你的输出是否使用了 %4d。

  C语言中，%d是按照原型输出，%4d表示数据宽度为4，不够就用空格补。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct node{double x,y;}a,b,c;
double min(double a,double b){return a<b?a:b;}
double max(double a,double b){return a>b?a:b;}
double area(node a,node b,node c){return fabs(a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y);}
int main()
{
    while(scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y)){
        if(!a.x&&!a.y&&!b.x&&!b.y&&!c.x&&!c.y) break;
        int minx=max(1,ceil(min(a.x,min(b.x,c.x)))),maxx=min(99,(int)max(a.x,max(b.x,c.x)));
        int miny=max(1,ceil(min(a.y,min(b.y,c.y)))),maxy=min(99,(int)max(a.y,max(b.y,c.y)));
        int cnt=0;
        double S=area(a,b,c);
        for(int i=minx;i<=maxx;++i)
            for(int j=miny;j<=maxy;++j){
                double tmp=area((node){i,j},a,b)+area((node){i,j},a,c)+area((node){i,j},b,c);
                if(fabs(S-tmp)<1e-8) cnt++;
            }
        printf("%4d\n",cnt);
    }
    return 0;
}