hdu 2948単純計算幾何学的判断点は三角形矩形の円形内にある

10150 ワード

ACM hdu ポイント位置

に言及
本質はタイトルのような計算ジオメトリです.2人でダーツゲームをして、いくつかの形のターゲットを提供しました.ダーツは試合ごとに3回ずつ投げます(Bob先手、Hannah後手)ダーツの得点は、1ダーツが何個のターゲットにあるかを示し、最後に勝者の名前を出力し、引き分けてTiedを出力する.まず、sがターゲットを表す個数を与え、その後、s行がターゲットを表す.Cは円形ターゲットを表し、円心座標と半径長を与える.Rは矩形ターゲットを表し、対角頂点の座標x 1問題解
直接シミュレーション判定点は円形内:点と円心の距離<=半径判定点は矩形内:点座標は対角頂点の間にある.すなわち(x 1<=x<=x 2,y 1<=y<=y 2)判断点が三角形内:点と三角形の各辺からなる三角形の面積=原三角形の面積
計算ジオメトリを習い始めたばかりで、コード変数関数の名前が少し長いので、許してください.

#include 
using namespace std;
typedef long long ll;

const double eps = 1e-6;
const double PI = acos(-1);
const int maxn = 1e3+5;

struct Point{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}

    //  +
    Point operator +(const Point &b)const
    {
        return Point(x+b.x,y+b.y);
    }
    //  -
    Point operator -(const Point &b)const
    {
        return Point(x-b.x,y-b.y);
    }
    //  
    double operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
    //  
    //P^Q>0,P Q      ；<0，P Q      ；=0，P，Q  ，       
    double operator ^(const Point &b)const
    {
        return x*b.y - b.x*y;
    }
};
typedef Point Vector;

struct Triangle{
    Point A,B,C;
}triangle[maxn];

struct Circle{
    Point O;
    double R;
}circle[maxn];

struct rectangle{
    Point A,B;
}rectangle[maxn];

//    ，    double eps        
int dcmp(double x)
{
    if(fabs(x)return 0;
    else
        return x<0?-1:1;
}
//   P      ABC 
bool InTriangle(Point A,Point B,Point C,Point P)
{
    double Sabc = fabs((B-A)^(C-A));
    double Spab = fabs((A-P)^(B-P));
    double Spac = fabs((A-P)^(C-P));
    double Spbc = fabs((B-P)^(C-P));
    return dcmp(Sabc-Spab-Spac-Spbc)==0;
}
//   P   O   R      
bool InCircle(Point O,double R,Point P)
{
    double pr = sqrt(pow(P.x-O.x,2)+pow(P.y-O.y,2));
    return dcmp(pr-R)<=0;
}
//   P   A，B        
bool InRectangle(Point A,Point B,Point P)
{
    return (dcmp(P.x-A.x)>=0&&dcmp(P.y-A.y)>=0&&dcmp(P.x-B.x)<=0&&dcmp(P.y-B.y)<=0);
}

int main()
{
    int t,triangle_num=0,circle_num=0,rectangle_num=0;
    char str[5];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        switch(str[0])
        {
        case 'C':
            scanf("%lf %lf %lf",&circle[circle_num].O.x,&circle[circle_num].O.y,&circle[circle_num].R);
            circle_num++;
            break;
        case 'R':
            scanf("%lf %lf %lf %lf",&rectangle[rectangle_num].A.x,&rectangle[rectangle_num].A.y,&rectangle[rectangle_num].B.x,&rectangle[rectangle_num].B.y);
            rectangle_num++;
            break;
        case 'T':
            scanf("%lf %lf %lf %lf %lf %lf",&triangle[triangle_num].A.x,&triangle[triangle_num].A.y,&triangle[triangle_num].B.x,&triangle[triangle_num].B.y,&triangle[triangle_num].C.x,&triangle[triangle_num].C.y);
            triangle_num++;
            break;
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        int ans1=0,ans2=0;
        Point tmp;
        for(int i=1;i<=3;i++)
        {
            scanf("%lf %lf",&tmp.x,&tmp.y);
            for(int j=0;jif(InTriangle(triangle[j].A,triangle[j].B,triangle[j].C,tmp)) ans1++;
            for(int j=0;jif(InRectangle(rectangle[j].A,rectangle[j].B,tmp)) ans1++;
            for(int j=0;jif(InCircle(circle[j].O,circle[j].R,tmp)) ans1++;
        }
        for(int i=1;i<=3;i++)
        {
            scanf("%lf %lf",&tmp.x,&tmp.y);
            for(int j=0;jif(InTriangle(triangle[j].A,triangle[j].B,triangle[j].C,tmp)) ans2++;
            for(int j=0;jif(InRectangle(rectangle[j].A,rectangle[j].B,tmp)) ans2++;
            for(int j=0;jif(InCircle(circle[j].O,circle[j].R,tmp)) ans2++;
        }
        if(ans1==ans2) printf("Tied
");
        else printf("%s
",ans1"Hannah" : "Bob");
    }
    return 0;
}

Emacs: 不要なバッファーを自動的にkillする

magitで新規ディレクトリ内のファイルを表示する