HDU 2948 Geometry Darts(点在圆,三角形,矩形内判定)

HDU 2948 Geometry Darts(点在圆,三角形,矩形内判定)

http://acm.hdu.edu.cn/showproblem.php?pid=2948

题意:

两个人比赛扔飞镖,现在有n个图形(圆,矩形,或三角形).他们进行k轮比赛,每轮比赛每人扔3次飞镖.一个飞镖的得分数等于该飞镖在多少个图形内.比较他们每轮的分数,输出他们每轮的比赛结果.

分析:

本题本质就是判断一个给定点是否在圆或矩形或三角形内.

判断点在圆内,只要看点到圆形的距离是否<=圆半径.

判断点在矩形内,只要看点坐标输入[x1,x2]和[y1,y2]范围.

判断点在三角形内,只要看点与三角形各边构成三角形的面积是否==三角形总面积.

之后比较二者得分即可.

注意:开始我精度eps取1e-10,直接WA.改成1e-6就对了.

用了vector容器,C++提交险些超时…g++提交没问题.

AC代码:

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const double eps=1e-6;//如果取1e-10就会WA
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){}
};
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;
}
/***以上为刘汝佳模板***/
struct Circle
{
    double x,y,r;
    bool InCircle(Point p)
    {
        double dist=(p.x-x)*(p.x-x)+(p.y-y)*(p.y-y);
        return dcmp(r*r-dist)>=0;
    }
};
struct Rectangle
{
    double x1,y1,x2,y2;
    bool InRectangle(Point p)
    {
        return dcmp(p.x-x2)<=0&&dcmp(p.x-x1)>=0&&dcmp(p.y-y2)<=0&&dcmp(p.y-y1)>=0;
    }
};
struct Triangle
{
    Point p[3];
    bool InTriangle(Point P)
    {
        double a1=fabs(Cross(P-p[0],p[0]-p[1]));
        double a2=fabs(Cross(P-p[1],p[1]-p[2]));
        double a3=fabs(Cross(P-p[2],p[2]-p[0]));
        double area=fabs(Cross(p[0]-p[1],p[1]-p[2]));
        return dcmp(a1+a2+a3-area)==0;
    }
};
vector<Circle> C;
vector<Rectangle> R;
vector<Triangle> T;


int main()
{
    int n,m;
    while(scanf("%d",&n)==1)
    {
        C.clear(),T.clear(),R.clear();
        for(int i=1;i<=n;++i)
        {
            char type;
            scanf(" %c",&type);
            if(type=='C')
            {
                Circle c1;
                scanf("%lf%lf%lf",&c1.x,&c1.y,&c1.r);
                C.push_back(c1);
            }
            else if(type=='R')
            {
                Rectangle r1;
                scanf("%lf%lf%lf%lf",&r1.x1,&r1.y1,&r1.x2,&r1.y2);
                R.push_back(r1);
            }
            else if(type=='T')
            {
                Triangle t1;
                for(int i=0;i<3;++i) scanf("%lf%lf",&t1.p[i].x,&t1.p[i].y);
                T.push_back(t1);
            }
        }
        scanf("%d",&m);
        while(m--)
        {
            int s1=0,s2=0;//两边的分数
            for(int i=0;i<3;i++)
            {
                Point p;
                scanf("%lf%lf",&p.x,&p.y);
                for(int j=0;j<C.size();++j)
                    if(C[j].InCircle(p)) s1++;
                for(int j=0;j<R.size();++j)
                    if(R[j].InRectangle(p)) s1++;
                for(int j=0;j<T.size();++j)
                    if(T[j].InTriangle(p)) s1++;
            }
            for(int i=0;i<3;i++)
            {
                Point p;
                scanf("%lf%lf",&p.x,&p.y);
                for(int j=0;j<C.size();++j)
                    if(C[j].InCircle(p)) s2++;
                for(int j=0;j<R.size();++j)
                    if(R[j].InRectangle(p)) s2++;
                for(int j=0;j<T.size();++j)
                    if(T[j].InTriangle(p)) s2++;
            }
            if(s1==s2) printf("Tied\n");
            else printf("%s\n",s1>s2?"Bob":"Hannah");
        }
    }
    return 0;
}