【点的定位】Save the Students! UVALive - 5984

蔚落 2022-06-09 12:38 135阅读 0赞

Think:  
1知识点：判断一个点是否在三角形内/圆形内/正方形内  
2题意：输入多个三角形和圆形和正方形，询问最终有多少个点在输入的三角形内或者圆形内或者正方形内

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    struct point{
       /*记录点的信息*/
        double x;
        double y;
    };
    
    struct v{
       /*记录边的信息*/
        point star;/*边的起点*/
        point en;/*边的终点*/
    };
    
    struct triangle{
       /*记录三角形信息*/
        point A;/*三角形的顶点A*/
        point B;/*三角形的顶点B*/
        point C;/*三角形的顶点C*/
    };
    triangle tre[104];
    int tr;
    
    struct square{
        int x;/*正方形左下角的横坐标*/
        int y;/*正方形左下角的纵坐标*/
        int l;/*正方形的边长*/
    };
    square squ[104];
    int sq;
    
    struct circle{
        int x;/*圆心的横坐标*/
        int y;/*圆心的纵坐标*/
        int r;/*圆的半径*/
    };
    circle cir[104];
    int ci;
    
    double crossProduct(v * v1, v * v2);/*向量叉积*/
    bool inTrianle(triangle t, point P);/*判断点是否在三角形内*/
    bool inSquare(square t, int x, int y);/*判断点是否在正方形内*/
    bool inCircle(circle t, int x, int y);/*判断点是否在圆内*/
    
    int main(){
        int T, n, i, j, k, num;
        char st[14];
        scanf("%d", &T);
        while(T--){
            tr = sq = ci = 0;
            scanf("%d", &n);
            while(n--){
                scanf("%s", st);
                if(st[0] == 'C'){
                    scanf("%d %d %d", &cir[ci].x, &cir[ci].y, &cir[ci].r);
                    ci++;
                }
                else if(st[0] == 'S'){
                    scanf("%d %d %d", &squ[sq].x, &squ[sq].y, &squ[sq].l);
                    sq++;
                }
                else {
                    scanf("%lf %lf %lf %lf %lf %lf", &tre[tr].A.x, &tre[tr].A.y, &tre[tr].B.x, &tre[tr].B.y, &tre[tr].C.x, &tre[tr].C.y);
                    tr++;
                }
            }
            num = 0;
            for(i = -200; i <= 200; i++){
                for(j = -200; j <= 200; j++){
                    bool flag = false;
                    for(k = 0; k < ci; k++){
                        if(inCircle(cir[k], i, j)){
                            flag = true;
                            break;
                        }
                    }
                    if(!flag){
                        for(k = 0; k < sq; k++){
                            if(inSquare(squ[k], i, j)){
                                flag = true;
                                break;
                            }
                        }
                    }
                    if(!flag){
                        point t;
                        for(k = 0; k < tr; k++){
                            t.x = (double)i, t.y = (double)j;
                            if(inTrianle(tre[k], t)){
                                flag = true;
                                break;
                            }
                        }
                    }
                    if(flag)
                        num++;
                }
            }
            printf("%d\n", num);
        }
        return 0;
    }
    double crossProduct(v * v1, v * v2){
        v vt1, vt2;
        double result = 0;
        vt1.star.x = 0;
        vt1.star.y = 0;
        vt1.en.x = v1->en.x - v1->star.x;
        vt1.en.y = v1->en.y - v1->star.y;
    
        vt2.star.x = 0;
        vt2.star.y = 0;
        vt2.en.x = v2->en.x - v2->star.x;
        vt2.en.y = v2->en.y - v2->star.y;
    
        result = vt1.en.x * vt2.en.y - vt2.en.x * vt1.en.y;
        return result;
    }
    bool inTrianle(triangle t, point p){
        v AB, AC, BC, PA, PB, PC;
        AB.star = t.A;
        AB.en = t.B;
        AC.star = t.A;
        AC.en = t.C;
        BC.star = t.B;
        BC.en = t.C;
        PA.star = p;
        PA.en = t.A;
        PB.star = p;
        PB.en = t.B;
        PC.star = p;
        PC.en = t.C;
    
        double Sabc = fabs(crossProduct(&AB, &AC));
        double Spab = fabs(crossProduct(&PA, &PB));
        double Spac = fabs(crossProduct(&PA, &PC));
        double Spbc = fabs(crossProduct(&PB, &PC));
        if(Sabc == Spab + Spac + Spbc)
            return true;
        else
            return false;
    }
    bool inSquare(square t, int x, int y){
        if(x >= t.x && x <= t.x+t.l && y >= t.y && y <= t.y+t.l)
            return true;
        else
            return false;
    }
    bool inCircle(circle t, int x, int y){
        int ans = (x-t.x)*(x-t.x) + (y-t.y)*(y-t.y);
        if(ans <= t.r*t.r)
            return true;
        else
            return false;
    }

[vjudge]: https://vjudge.net/problem/UVALive-5984