第 20 次 CSP认证 202009-4 星际旅行

1.写在前面

考试时候没做出来，第三题debug太久，md 现在75分，超时，不知道哪里有改进空间，可能是算法不太行，数学好菜啊

2.思路

想法是把两个点和圆心构成一个三角形，三角形的三边定义成 moa,mob,juli即向量a的模，向量b的模，ab两点的距离。用向量乘积的定理，可以求出两个向量的夹角jiaodu，用面积公式计算出高gao，计算高是否在三角形内部就要计算是否是钝角三角形，钝角三角形一定不在球内，返回距离。判断高与半径的关系，不在球内则返回距离。 若两点连线经过球，则路径是圆弧加两个切线长。

3.代码

import java.util.Scanner; public class Main { public static int m; public static int n; public static int r; public static double getans(int[] point1,int[] point2) { int i=0; int xiangliangji=0; double moji=0; double moa=0,mob=0; double juli=0; double jiaodu=0; double gao=0; double ret=0; for(i=0;i<n;i++) { xiangliangji+=point1[i]*point2[i]; moa+=point1[i]*point1[i]; mob+=point2[i]*point2[i]; juli+=(point1[i]-point2[i])*(point1[i]-point2[i]); } moa=Math.sqrt(moa); mob=Math.sqrt(mob); juli=Math.sqrt(juli); moji=moa*mob; if(xiangliangji/moji<-1||xiangliangji/moji>1) moji=Math.round(moji); jiaodu=Math.acos(xiangliangji/moji); gao=moa*mob*Math.sin(jiaodu)/juli; double jiaoa=Math.asin(mob*Math.sin(jiaodu)/juli); double jiaob=Math.asin(moa*Math.sin(jiaodu)/juli); if((jiaoa+jiaodu)<Math.PI/2||(jiaob+jiaodu)<Math.PI/2) { return juli; } if(gao>r) return juli; jiaodu-=Math.acos(r/moa); jiaodu-=Math.acos(r/mob); double juli1,juli2; if(moa>r) juli1=Math.sqrt(moa*moa-r*r); else juli1=0; if(mob>r) juli2=Math.sqrt(mob*mob-r*r); else juli2=0; ret=juli1+juli2+r*jiaodu; return ret; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); int[][] inp=new int[m][n]; int[] cen=new int[n]; double[][] ans=new double[m][m]; r=sc.nextInt(); int i,j; for(i=0;i<n;i++) cen[i]=sc.nextInt(); for(i=0;i<m;i++) { for(j=0;j<n;j++) { inp[i][j]=sc.nextInt()-cen[j]; } } double ret=0; for(i=0;i<m;i++) { ret=0; for(j=0;j<i;j++) { ret+=ans[i][j]; } ans[i][i]=0; for(j=i+1;j<m;j++) { ans[i][j]=getans(inp[i],inp[j]); ans[j][i]=ans[i][j]; ret+=ans[i][j]; } System.out.println(ret); } } }