首页 > 其他分享 >【CSP】202009-4 星际旅行 90%

【CSP】202009-4 星际旅行 90%

时间:2024-04-14 14:22:22浏览次数:25  
标签:return int up 90% 球体 const include CSP 202009

题目大意:

n维空间内有一半径为r的球体,空间中球体之外有m个点,在不穿过球体的条件下求这m个点两两间的最短曲线距离。

分析:

显然有两种情况:1.两点连线不经过球体;2.两点连线穿过球体。

第一种情况显然,考虑第二种情况:将球心、两点作为研究平面,可以发现最短曲线一定包括两条线段和一段圆弧。由两点间直线最短可知,如果圆弧左右端点如果不是切点的话一定会形成三条(曲)边,和一定大于切线段长度。

之后,主要使用余弦定理和反三角函数就可以处理问题,这部分主要考察代码而不是思维能力(所以当我知道第一次编译并且编译过的时候只剩1个bug的时候我感觉我很强大(逃))

需要注意的是,cmath库中的acos对于浮点数运算自带的误差不能很好的处理,当数值接近1或-1的时候要手动处理一下,防止微小越界出现NaN的情况。

最后,由于是计算两两间距离,可以用数组存储结果进行一点小优化(虽然也只是85->90)。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>
#include <cmath>

#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=r;i>=l;i--)

typedef long long ll;

using namespace std;

inline int _max(const int& a,const int& b){return a>b?a:b;}
inline int _min(const int& a,const int& b){return a<b?a:b;}

#define PI 3.14159265

const int MAXN = 120;
const int MAXM = 2020;

inline bool equal(const double& a, const double &b){
    if(a >= b)
        return ((a-b)<0.00000000001)?1:0;
    return ((b-a)<0.00000000001)?1:0;
}

int n,m;
double r;

struct Vec{
    double w[MAXN];
    double mod,dmod;
    Vec():mod(0),dmod(0){memset(w,0,sizeof(w));}
    void print(){
        printf("[");
        up(1,n,i){
            printf("%.4f, ",w[i]);
        }
        printf("]\n");
    }
}v[MAXM];

inline double mod(Vec& a){
    double ret = 0;
    up(1,n,i)
        ret += a.w[i]*a.w[i];
    ret = sqrt(ret);
    a.mod = ret;
    if(a.mod) a.dmod = 1/a.mod;
    return a.mod;
}

Vec operator - (const Vec& x){
    Vec ret;
    up(1,n,i)
        ret.w[i] = -x.w[i];
    ret.mod = x.mod;
    ret.dmod = x.dmod;
    return ret;
}

Vec operator - (const Vec& x,const Vec& y){
    Vec ret;
    up(1,n,i)
        ret.w[i] = x.w[i] - y.w[i];
    mod(ret);
    return ret;
}

double dot(const Vec& a, const Vec& b){
    double ret = 0.f;
    up(1,n,i)
        ret += a.w[i]*b.w[i];
    return ret;
}

double getangle(const Vec& a, const Vec& b){
    double Cos = dot(a,b)*a.dmod*b.dmod;
    double ret = acos(Cos);
    if(equal(Cos,1.f) || equal(Cos,-1.f)){
        ret = (PI-Cos*PI)/2;
    }
    return ret;
}

inline double r2a(const double& a){
    return a*180/PI;
}

inline double pow2(const double& a){
    return a*a;
}

bool ifcross(const Vec& a, const Vec& b){//判断两点连线是否与圆相交
    Vec l = b-a;//如果某点与圆心连线与两点连线的夹角大于90度那么不可能相交
    double a1 = getangle(-a,l),a2 = getangle(-b,-l);
    //printf("某点与圆心连线与两点连线的夹角分别为%.4f,%.4f\n",r2a(a1),r2a(a2));
    if(a1 > PI/2 || a2 > PI/2) return false;
    double d = a.mod*sin(a1);
    if(d <= r) return true;
    return false;
}

double solve(const Vec& a, const Vec& b){
    if(!ifcross(a,b))
        return (a-b).mod;
    double aa,a1,a2,rem,d1,d2,ans = 0;
    aa = getangle(a,b);
    a1 = acos(r/a.mod);
    a2 = acos(r/b.mod);
    rem = aa-a1-a2;
    rem *= r;
    d1 = sqrt(pow2(a.mod)-pow2(r));
    d2 = sqrt(pow2(b.mod)-pow2(r));
    ans = rem+d1+d2;
    //printf("与圆心连线夹角为%.4f,切线夹角分别为%.4f,%.4f\n",aa,a1,a2);
    return ans;
}

double ans[MAXM][MAXM];

int main()
{
    //freopen("y.in","r",stdin);

    ios::sync_with_stdio(false);

    cin>>n>>m;
    cin>>r;
    Vec o;
    up(1,n,i)
        cin>>o.w[i];
    
    up(1,m,i){
        up(1,n,j){
            cin>>v[i].w[j];
        }

        v[i] = v[i] - o;
        mod(v[i]);
    }

    up(1,m,i){
        double sum = 0;
        up(1,m,j){
            if(i == j) continue;
            //printf("正在计算P%d,P%d之间的最短距离\n",i,j);
            if(j < i) sum += ans[j][i];
            else {ans[i][j] = solve(v[i],v[j]);
                sum += ans[i][j];
            }
        }
        printf("%.12f\n",sum);
    }




    return 0;
}
90

 

标签:return,int,up,90%,球体,const,include,CSP,202009
From: https://www.cnblogs.com/dudujerry/p/18134104

相关文章

  • CCF CSP 2018年9月第二题-买菜
    问题描述小H和小W来到了一条街上,两人分开买菜,他们买菜的过程可以描述为,去店里买一些菜然后去旁边的一个广场把菜装上车,两人都要买n种菜,所以也都要装n次车。具体的,对于小H来说有n个不相交的时间段[a1,b1],[a2,b2]...[an,bn]在装车,对于小W来说有n个不相交的时间段[c1,d1],[c2,d......
  • P1908 逆序对
    原题链接题解本质:求一个数前面有几个数大于它,我们把序列分成几段,然后对每段分别进行排序,然后找出这个数在前面已经排好序中的序列里有几个大于它code#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[500005],b[500005],c[500005];//a-original......
  • ubuntu22 安装3090驱动
    1.执行nvidia-smi-a查询显卡资源报错aptinstallnvidia-utils-535-serveraptinstallnvidia-utils-5352.安装驱动nvdia-smi提示未安装驱动预先安装系统:ububtu22.04LTS查看可安装驱动版本:#ubuntu-driversdevicesERROR:root:aplaycommandnotfound==/sys/devices/pci000......
  • CF 1900 选做
    byDuck.CF1012BChemicaltable双倍经验eJOI2018同名题目。经典套路题。我们把行号和列号建成二分图,那么这个连边条件可以看作,\((r_1,c_1),(r_1,c_2),(r_2,c_2)\)之间有边后就会自然导致\(r_2,c_2\)连通。最后的目标是让所有点联通。并查集维护连通性,答案就是连通块数......
  • 【CSP】202012-4 食材运输 70% 一点思路
    对于K==M的情况,问题重点是:如何统计从某点出发,遍历需要某食材的所有酒店最小权重和。考虑到N规模很小,因此可以直接枚举从每个点出发的权重和,问题就转化为如何求从某点出发,遍历某食材的权重和。由于图为一棵树,所有该权重和是唯一的。有两个限制条件:如何知道某食材的全部酒店已经经......
  • Rule 90
    Rule90isaone-dimensionalcellularautomatonwithinterestingproperties.Therulesaresimple.Thereisaone-dimensionalarrayofcells(onoroff).Ateachtimestep,thenextstateofeachcellistheXORofthecell'stwocurrentneighbours.......
  • golang实现R6900路由器外网IP更新通知程序
    程序一分钟执行一次,检测路由器外网IP地址变更则自动发送邮件,使用网易126smtp协议发送邮件,邮箱地址及授权码请自行替换,getIp函数中的grep根据自己的网卡信息调试替换R6900路由器的交叉编译语句:CGO_ENABLED=0GOOS=linuxGOARCH=armGOARM=5gobuildxxxx.go1234567......
  • Cisco Nexus 9000 Series Switches, NX-OS Standalone 10.4(3)F and ACI Mode 16.0(5h
    CiscoNexus9000SeriesSwitches,NX-OSStandalone10.4(3)FandACIMode16.0(5h)includeApplicationPolicyInfrastructureController(APIC)Release6.0(5h)请访问原文链接:CiscoNexus9000SeriesSwitches,NX-OSStandalone10.4(3)FandACIMode16.0(5h),查看最......
  • CF1907B YetnotherrokenKeoard 题解
    比较简单,建议评橙。题面。思路对于每个给定的字符串,用两个大根堆来分别记录小写字母与大写字母,注意这里记录时不要记录大写的B和小写的b。每当出现一个B时,从记录大写字母的大根堆中取出目前最后录入的大写字母的位置,标记,接着弹出堆顶元素,标记。小写字母同理。以上操作在......
  • P9750 [CSP-J 2023] 一元二次方程 题解
    题面。直接依照题意模拟即可,注意细节。细节第一注意输出分式时分母为\(1\)不输出,分子为\(0\)直接输出零且不带正负号。第二约分时,\(gcd\)内的两个数应该都是非负实数。第三可以单独输出符号,注意别有多余的符号。第四当方程有两根且均是有理数时,要根据\(2a\)的正......