E - Naive and Silly Muggles（简单计算几何）

Bertha 。 2024-04-17 05:25 10阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
Three wizards are doing a experiment. To avoid from bothering, a special magic is set around them. The magic forms a circle, which covers those three wizards, in other words, all of them are inside or on the border of the circle. And due to save the magic power, circle’s area should as smaller as it could be.  
Naive and silly “muggles”(who have no talents in magic) should absolutely not get into the circle, nor even on its border, or they will be in danger.  
Given the position of a muggle, is he safe, or in serious danger?  
Input  
The first line has a number T (T <= 10) , indicating the number of test cases.  
For each test case there are four lines. Three lines come each with two integers x i and y i (|x i, y i| <= 10), indicating the three wizards’ positions. Then a single line with two numbers q x and q y (|q x, q y| <= 10), indicating the muggle’s position.  
Output  
For test case X, output "Case \#X: " first, then output “Danger” or “Safe”.  
Sample Input  
3  
0 0  
2 0  
1 2  
1 -0.5  
0 0  
2 0  
1 2  
1 -0.6  
0 0  
3 0  
1 1  
1 -1.5

Sample Output  
Case \#1: Danger  
Case \#2: Safe  
Case \#3: Safe

分析：  
先驱知识：  
三角形外心求法： https://blog.csdn.net/u010141928/article/details/88942989  
克拉默法则求解二元一次方程组（线性代数，可怜我的80多分，现在连这个都记不起来了）：  
https://zhidao.baidu.com/question/418173189.html  
判断一个三角形是钝角还是锐角三角形：  
https://www.zybang.com/question/d4ae49cc2bca20b577fe301338f5843b.html  
此三个先驱知识，都是十分简单的知识了。实在可怜我的数学太差了。

在我们队做这个题的时候（训练赛），队友提出用半径列方程组化简来求出圆心坐标。  
我还特意的去化简了这个方程组，最终得到了一个二元一次方程组。如果我们继续这个思路一定是没得问题的。可是，我却选择了用斜率直接的关系表示出两条直线求交点。于是我们在连样例都过不了的路上，不断挣扎。我好菜呀。  
看到题目，我清楚地认知到一定要避免除法运算。~~然而我却用斜率？？？ 我在干啥勒  
好吧，其实就算用了半径求，我们队还是过不了样例。因为我们压根没考虑到最大边的中点也是可能做圆心的（这就取决于这个三角形是不是锐角三角形了）。  
样例第三个，便是中点做圆心的。  
为啥勒，仔细想一下应该是没问题的。

所以，现在我们的目标明确了。  
1，判断是不是锐角三角形。是则直接最大边中点做圆心。否则，外心做圆心。  
2，求出外心，这里推荐看上面那篇博客。有推理过程。很好。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    double a[4][2];
    double x,y,midx,midy,R;
    int T;
    
    double dist(double x,double y,double x1,double y1)
    {
        return (x - x1) * (x - x1) + (y - y1) * (y - y1);
    }
    
    int check()
    {
        double dis[4];
        dis[1] = dist(a[1][0],a[1][1],a[2][0],a[2][1]);
        dis[2] = dist(a[1][0],a[1][1],a[3][0],a[3][1]);
        dis[3] = dist(a[2][0],a[2][1],a[3][0],a[3][1]);
        if(dis[1] > dis[2] && dis[1] > dis[3])
        {
            midx = (a[1][0] + a[2][0]) / 2;
            midy = (a[1][1] + a[2][1]) / 2;
            R = dist(midx,midy,a[1][0],a[1][1]);
        }
        if(dis[2] > dis[1] && dis[2] > dis[3])
        {
            midx = (a[1][0] + a[3][0]) / 2;
            midy = (a[1][1] + a[3][1]) / 2;
            R = dist(midx,midy,a[1][0],a[1][1]);
        }
        if(dis[3] > dis[1] && dis[3] > dis[2])
        {
            midx = (a[2][0] + a[3][0]) / 2;
            midy = (a[2][1] + a[3][1]) / 2;
            R = dist(midx,midy,a[2][0],a[2][1]);
        }
        sort(dis + 1,dis + 4);
        return dis[1] + dis[2] < dis[3];
    }
    
    int main()
    {
        scanf("%d",&T);int cnt = 1;
        while(T --)
        {
            for(int i = 1; i <= 3; i ++)
                scanf("%lf%lf",&a[i][0],&a[i][1]);
            scanf("%lf%lf",&x,&y);
            if(check() == 1) /// 圆心在两点的中线上
            {
                double r = dist(midx,midy,x,y);
                //printf("%.5lf %.5lf\n",r,R);
                if(r <= R)
                    printf("Case #%d: Danger\n",cnt ++);
                else
                    printf("Case #%d: Safe\n",cnt ++);
                continue;
            }
            double A1 = 2 * (a[1][0] - a[2][0]);
            double B1 = 2 * (a[1][1] - a[2][1]);
            double C1 = a[1][1] * a[1][1] + a[1][0] * a[1][0] - a[2][0] * a[2][0] - a[2][1] * a[2][1];
            double A2 = 2 * (a[1][0] - a[3][0]);
            double B2 = 2 * (a[1][1] - a[3][1]);
            double C2 = a[1][1] * a[1][1] + a[1][0] * a[1][0] - a[3][0] * a[3][0] - a[3][1] * a[3][1];
            double D = A1 * B2 - A2 * B1;
            double Dx = C1 * B2 - B1 * C2;
            double Dy = A1 * C2 - A2 * C1;
            midx = Dx / D; midy = Dy / D;
            R = dist(midx,midy,a[1][0],a[1][1]);
            double r = dist(midx,midy,x,y);
            if(r <= R)
                    printf("Case #%d: Danger\n",cnt ++);
                else
                    printf("Case #%d: Safe\n",cnt ++);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/