【CSP】202009-4 星际旅行(计算几何)

56 阅读 0 评论 37 点赞

我是靠谱客的博主潇洒嚓茶，最近开发中收集的这篇文章主要介绍【CSP】202009-4 星际旅行(计算几何)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

该题本质上并不难，只要你理解了它的核心——刨析直线与圆的关系。
在以前的高中课本中，想必大家都学过，过三点必确定一个平面，显然这里的三点我们取黑体中心，及任意两个旅行点。这样一来超维情况便只剩下解决两点之间的距离，显然把相对应的维坐标相减取二次方，再都加起来，最后开方根即是最终答案。
接下来我们刨析一下直线与圆的关系。显然，直线与圆只有相交相切相离三种情况，而在取的任意两个旅行点连起来的直线与原点所在平面截下来的圆相切或相离时，由两点之间直线最短可知最短旅行距离。而在相交情况下，则要分两种情况，两旅行点连起来的线段是否与圆相交，若否，显然最短距离也是该线段，若不是则取两点做圆的切线，分别取两点到切点的距离（利用直角），再加上中间一小段圆弧的距离（l=ar公式求得，其中涉及到角的求解可利用三角函数去求得）这样即求到最短距离。而这相交线的判断标准看三点构成的三角形除圆心角外，是否存在钝角，若存在钝角该线段就在圆外。
总而言之，通过给出的数据我们可以得到所有边长，而从边长出发，我们又可以根据公式得到我们需要的判断数据。
主体代码如下

/*
 * @Author: csc
 * @Date: 2020-12-14 17:29:08
 * @LastEditTime: 2020-12-19 21:35:35
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: codecsp2009_3.cpp
 */
#include <bits/stdc++.h>
const int N = 2010;
const int M = 5000;
const int mod = 998244353;
typedef long long int ll;

using namespace std;

int n, m;
int r;
double x;
double dis[N],d[N];
int o[N],p[N][N];
double ans[N][N];

int main()
{
    cin >> n >> m >> r;
    for (int i = 0; i < n; ++i)
        cin >> o[i];
    for (int j = 0; j < m; ++j)
    {
        x = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> p[j][i];
            x += (p[j][i] - o[i]) * (p[j][i] - o[i]);
        }
        dis[j] = sqrt(x);
        d[j] = sqrt(x-r*r);
    }

    for (int i = 0; i < m; ++i)
    {
        for (int j = i + 1; j < m; ++j)
        {
            int res = 0;
            for (int k = 0; k < n; ++k)
                res += (p[i][k] - p[j][k]) * (p[i][k] - p[j][k]);
            x = sqrt(res);
            double P = (dis[i] + dis[j] + x) / 2;
            double s = sqrt(P * (P - x) * (P - dis[i]) * (P - dis[j]));
            double h = 2 * s / x;
            if (h >= r)
            {
                ans[i][j] = ans[j][i] = x;
            }
            else
            {
                if ((dis[i] * dis[i] >= x * x + dis[j] * dis[j]) || (dis[j] * dis[j] >= x * x + dis[i] * dis[i]))
                {
                    ans[i][j] = ans[j][i] = x;
                }
                else
                {
                    double a = acos((dis[i] * dis[i] + dis[j] * dis[j] - x * x) / (2 * dis[i] * dis[j]));
                    double a1 = acos(r / dis[i]);
                    double a2 = acos(r / dis[j]);
                    ans[i][j] = ans[j][i] = r * (a - a1 - a2) + d[i] + d[j];
                }
            }
        }
    }
    for (int i = 0; i < m; cout << endl, ++i)
    {
        double res = 0.0;
        for (int j = 0; j < m; ++j)
        {
            if (i == j)
                continue;
            res += ans[i][j];
        }
        printf("%.14lf", res);
    }

    return 0;
}