UVA 143 Orchard Trees(判断点在三角形内)

UVA 143 Orchard Trees(判断点在三角形内)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=79

题意:

在一个[0,100]坐标范围的二维平面中,任意给你三角形的三点,问你[1,99]范围的整点坐标有多少个 在该三角形内部(在边上也算).

分析:

首先我们直接枚举所有的1-99整点,然后判断该点是否在三角形内部即可.

判断一个点是否在三角形内部可以用面积也可以用向量叉积方向的方法. 代码中我的面积判断.

题中给的3点如果共线的话, 那么只有一个整点也跟这3点共线且要在这3点构成的线段内才行.这点需要注意. 所以需要多判断一下该点的坐标是否在3点的坐标范围的最大最小值范围内.

我把double声明成了int, 结果WA了半天,真是醉了.

AC代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
}A,B,C;

typedef Point Vector;

Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double Area(Point A,Point B,Point C)
{
    return fabs(Cross(A-B,A-C))/2;
}
bool InTriangle(Point P,Point A,Point B,Point C)
{
    double max_x=max(A.x,max(B.x,C.x));//我真是醉了,这里声明成了int WA了我半天
    double min_x=min(A.x,min(B.x,C.x));
    double max_y=max(A.y,max(B.y,C.y));
    double min_y=min(A.y,min(B.y,C.y));
    double s=Area(A,B,C);
    if( dcmp( Area(P,A,B)+Area(P,A,C)+Area(P,B,C)-Area(A,B,C) ) ==0 )
    {
        if(dcmp(s)>0) return true;//ABC三点不共线

        return dcmp(P.x-min_x)>=0 && dcmp(P.x-max_x)<=0 && dcmp(P.y-min_y)>=0 && dcmp(P.y-max_y)<=0;//三点共线且P在线段ABC内
    }
    return false;
}

int main()
{
    while(scanf("%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y)==6)
    {
        if(A.x==0 && A.y==0 && B.x==0 && B.y==0 && C.x==0 && C.y==0) break;
        int ans=0;//三角形内点数
        for(int i=1;i<=99;++i)
        for(int j=1;j<=99;++j)
        {
            Point P(i,j);
            if(InTriangle(P,A,B,C)) ++ans;
        }
        printf("%4d\n",ans);
    }
    return 0;
}