星际旅行

星际旅行 ccf202009-4

ccf刷题记录
ccf202009-4
考试半年后复盘，仍然卡了好久。
简单的数学题，第一次因为时间卡了只有35。
后面参考某大佬帖发现少考虑两种不在圈内的情况，40。
调试很久失败，后重新写了一遍才过。
还是要有好的编码习惯。

#include <iostream>
#include <cmath>
#include <vector>
#define ll long long
using namespace std;

long long m, n, r;

vector<long long> O;
vector<long long> p[2000];

long double dis[2000][2000];
long long toCent[2000];

void read() {
	
	cin >> n >> m >> r;
	int th;
	for (int i = 0; i < n; i++) {
		
		cin >> th;
		O.push_back(th);
	}
	
	for (int i = 0; i < m; i++) {
		
		for (int j = 0; j < n; j++) {
			
			cin >> th;
			p[i].push_back(th-O[j]);
		}
	}
}

long long calDis2(int a, int b) {
	
	long long thAns = 0;
	for (int i = 0; i < n; i++) {
		
		thAns += (p[a][i]-p[b][i])*(p[a][i]-p[b][i]);
	}
	
	return thAns;
}

void pre() {
	
	for (int i = 0; i < m; i++) {
		
		long long thAns = 0;
		for (int j = 0; j < n; j++) {
			
			thAns += p[i][j]*p[i][j];
		}
		toCent[i] = thAns;
	}
}

bool isOut(int posA, int posB) {
	
	long long thDis2 = 0;
	double ao = sqrt(toCent[posA]);
	double bo = sqrt(toCent[posB]);
	double ab = sqrt(calDis2(posA, posB));
	
	double thp = (ao+bo+ab)/2;
	double h = sqrt(thp*(thp-ao)*(thp-bo)*(thp-ab))*2/ab;
	
	ll vecv1 = 0, vecv2 = 0;
	
	for (int i = 0; i < n; i++) {
		
		vecv1 += p[posA][i] * (p[posB][i]-p[posA][i]);
		vecv2 += p[posB][i] * (p[posA][i]-p[posB][i]);
	}
	
	return (h>r || vecv1>0 || vecv2>0);
}

double getDis(int posA, int posB) {
	
	if (isOut(posA, posB)) {
		
		return sqrt(calDis2(posA, posB));
	}
	else {
		
		long long mulAB = 0;
		for (int i = 0; i < n; i++) {
			
			mulAB += p[posA][i] * p[posB][i];
		}
		double radiAB = 0;
		if (mulAB * mulAB == toCent[posA] * toCent[posB]) {
			
			if (mulAB > 0) {
				
				radiAB = 0;
			}
			else {
				
				radiAB = 3.141592653;
			}
		}
		else {
			
			radiAB = acos(mulAB/(sqrt(toCent[posA]*toCent[posB])));
		}
		
		double radiAh = 0, radiBh = 0;
		radiAh = acos(r/sqrt(toCent[posA]));
		radiBh = acos(r/sqrt(toCent[posB]));
		
		double ans = (radiAB-radiAh-radiBh)*r + sqrt(toCent[posA]-r*r) + sqrt(toCent[posB]-r*r);
		return ans;
	}
}

int main() {
	
//	freopen("D:\shuru.txt", "r", stdin);
	
	read();
	pre();
	for (int i = 0; i < m; i++) {
		
		
		for (int j = i + 1; j < m; j++) {
			
			double thLen = getDis(i, j);
			dis[i][j] = thLen;
			dis[j][i] = thLen;
		}
	}
	
	for (int i = 0; i < m; i++) {
		
		double thAns = 0;
		for (int j = 0; j < m; j++) {
			
			if (i != j) {
				
				thAns += dis[i][j];
			}
		}
		printf("%.14fn", thAns);
	}
	return 0;
} 

最后

以上就是柔弱天空为你收集整理的星际旅行的全部内容，希望文章能够帮你解决星际旅行所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。