首页 > 代码库 > poj 2587(球面距离)
poj 2587(球面距离)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; bool vis[1000]; double x[1000],y[1000]; int n; int cnt; struct node{ int u,v; double dis; }edge[500000]; int cmp(node a,node b) { return a.dis>b.dis; } void cul(int u,int v) { edge[cnt].u=u; edge[cnt].v=v; double l1=x[u],d1=y[u],l2=x[v],d2=y[v]; double p = acos(-1.0); l1 *= p/180.0; d1 *= p/180.0; l2 *= p/180.0; d2 *= p/180.0; edge[cnt].dis=acos(cos(l1)*cos(l2)*cos(d1-d2)+sin(l1)*sin(l2)); cnt++; } int main() { memset(vis,true,sizeof vis); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf%lf",&x[i],&y[i]); cnt=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { cul(i,j); } sort(edge,edge+cnt,cmp); int num=0; for(int i=0;i<cnt;i++) { if(vis[edge[i].u]) { num++; vis[edge[i].u]=false; } if(num==n-1) break; if(vis[edge[i].v]) { num++; vis[edge[i].v]=false; } if(num==n-1) break; } for(int i=0;i<n;i++) if(vis[i]){ printf("%.2lf %.2lf\n",x[i],y[i]); break; } return 0; }
球面距离推导,转载自他人
poj 2587(球面距离)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。