题解 - Vijos

3

Sky1231 (sky1231) LV 10 @ 2020-10-11 10:24:23

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    const double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
    const double pi=3.14159265359,etr=6374;
    
    struct edge
    {
        int x,y;
        double d;
    };
    
    int cmp_edge(edge a,edge b)
    {
        return a.x<b.x;
    }
    
    struct posi
    {
        double we,ns;
        
        void read()
        {
            double wes=1,nss=1;
            char s[100];
            memset(s,0,sizeof(s));
            for (int i=0;i<100;i++)
            {
                s[i]=getchar();
                if (s[i]=='W')
                    wes=-1;
                else if (s[i]=='S')
                    nss=-1;
                if ('A'<=s[i]&&s[i]<='Z')
                    s[i--]=0;
                if (s[i]=='\n')
                    break;
            }
            sscanf(s,"%lf%lf",&we,&ns);
            we=wes*we*pi/180,ns=nss*ns*pi/180;
        }
    };
    
    double sqr(double x)
    {
        return x*x;
    }
    
    double dist(posi a,posi b)
    {
        double ax,ay,az,bx,by,bz;
        az=sin(a.ns),bz=sin(b.ns);
        double arl=cos(a.ns),brl=cos(b.ns);
        ax=arl*cos(a.we),ay=arl*sin(a.we),bx=brl*cos(b.we),by=brl*sin(b.we);
        double cosv=(2-sqr(ax-bx)-sqr(ay-by)-sqr(az-bz))/2;
        return acos(cosv)*etr;
    }
    
    int n;
    vector<int> b;
    vector<double> dis;
    vector<posi> a;
    vector<edge> e;
    deque<int> q;
    
    void main()
    {
        scanf("%d\n",&n);
        a.resize(n);
        for (int i=0;i<a.size();i++)
            a[i].read();
        e.clear();
        for (int x,y;~scanf("%d%d",&x,&y);)
        {
            edge temp;
            temp.x=--x,temp.y=--y,temp.d=dist(a[x],a[y]);
            e.push_back(temp);
        }
        sort(&e[0],&e[e.size()],cmp_edge);
        b.resize(n,-1);
        b[e[0].x]=0;
        for (int i=1;i<e.size();i++)
            if (e[i-1].x<e[i].x)
                b[e[i].x]=i;
        for (dis.resize(n,oo_max),dis[0]=0,q.clear(),q.push_back(0);!q.empty();q.pop_front())
            for (int i=b[q.front()];e[i].x==q.front();i++)
                if (dis[e[i].x]+e[i].d<dis[e[i].y])
                    dis[e[i].y]=dis[e[i].x]+e[i].d,q.push_back(e[i].y);
        if (dis[n-1]==oo_max)
            printf("Impossible\n");
        else
            printf("%.2lf\n",dis[n-1]);
    }
}

int main()
{
    dts::main();
}

0

real_hdsy_gyz LV 10 @ 2022-02-27 15:56:41

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
const double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
const double pi=3.14159265359,etr=6374;

struct edge
{
int x,y;
double d;
};

int cmp_edge(edge a,edge b)
{
return a.x<b.x;
}

struct posi
{
double we,ns;

void read()
{
double wes=1,nss=1;
char s[100];
memset(s,0,sizeof(s));
for (int i=0;i<100;i++)
{
s[i]=getchar();
if (s[i]=='W')
wes=-1;
else if (s[i]=='S')
nss=-1;
if ('A'<=s[i]&&s[i]<='Z')
s[i--]=0;
if (s[i]=='\n')
break;
}
sscanf(s,"%lf%lf",&we,&ns);
we=wes*we*pi/180,ns=nss*ns*pi/180;
}
};

double sqr(double x)
{
return x*x;
}

double dist(posi a,posi b)
{
double ax,ay,az,bx,by,bz;
az=sin(a.ns),bz=sin(b.ns);
double arl=cos(a.ns),brl=cos(b.ns);
ax=arl*cos(a.we),ay=arl*sin(a.we),bx=brl*cos(b.we),by=brl*sin(b.we);
double cosv=(2-sqr(ax-bx)-sqr(ay-by)-sqr(az-bz))/2;
return acos(cosv)*etr;
}

int n;
vector<int> b;
vector<double> dis;
vector<posi> a;
vector<edge> e;
deque<int> q;

void main()
{
scanf("%d\n",&n);
a.resize(n);
for (int i=0;i<a.size();i++)
a[i].read();
e.clear();
for (int x,y;~scanf("%d%d",&x,&y);)
{
edge temp;
temp.x=--x,temp.y=--y,temp.d=dist(a[x],a[y]);
e.push_back(temp);
}
sort(&e[0],&e[e.size()],cmp_edge);
b.resize(n,-1);
b[e[0].x]=0;
for (int i=1;i<e.size();i++)
if (e[i-1].x<e[i].x)
b[e[i].x]=i;
for (dis.resize(n,oo_max),dis[0]=0,q.clear(),q.push_back(0);!q.empty();q.pop_front())
for (int i=b[q.front()];e[i].x==q.front();i++)
if (dis[e[i].x]+e[i].d<dis[e[i].y])
dis[e[i].y]=dis[e[i].x]+e[i].d,q.push_back(e[i].y);
if (dis[n-1]==oo_max)
printf("Impossible\n");
else
printf("%.2lf\n",dis[n-1]);
}
}

int main()
{
dts::main();
}
Copy
0

naive!! LV 8 @ 4 年前
首先这道题似乎用向量点乘不行，精度较低。
还有似乎有些歧义，同一个经纬位置上的点竟然不联通。这个...
以及最后两个点的数据是给满了的，不要侥幸少开。
没错以上就是蒟蒻我提交了几十次的原因QAQ
最后是先转化为直角坐标，两点和球心连成三角形，再用余弦定理求出角度算球面距离。

0

ipip2005 LV 10 @ 13 年前
N次提交，终于过了，PASCAL的同志别看题目下面的注释了，Uses math语句，根本不能用，因为禁用的原因，这又是一道语言歧视类题目。

但我是PASCAL的，还是过了此题，在讨论区有我所给出的以知经纬度求球面短弧长的公式，C要过的话直接套用就可以，PASCAL如果要过，就必须用二分！

求出两点关于球心的角度后，本来的下一步是arccos(a) (a)为角度

PASCAL的话要二分a，近似到小数点后七八位左右。

注意cos函数的单调性，-pi~0单调增，0~pi单调增，分两次二分，求最接近的解。

最后提醒一下，SPFA的队列开500万左右才可以，先开100万第9个WA了

-1

Goodhao LV 10 @ 3 年前
double get(point a,point b) {
double dx=abs(a.x-b.x),dy=abs(a.y-b.y);
return R*2*asin(sqrt(sin(dx/2)*sin(dx/2)+cos(a.x)*cos(b.x)*sin(dy/2)*sin(dy/2)));
}
Copy
https://zh.wikipedia.org/wiki/%E5%A4%A7%E5%9C%86%E8%B7%9D%E7%A6%BB
为什么这样会WA啊，这个公式对不对啊

-1

wang_yanheng LV 10 @ 6 年前
楼下的是脑抽么!?
用SPFA速度很快，关键在建图。我是这样做的：

读入点的时候计算空间坐标
+ coord[i][Y] = RADIUS · sin(RAD(NS))
+ coord[i][X] = RADIUS · cos(RAD(NS)) · cos(RAD(EW))
+ coord[i][Z] = RADIUS · cos(RAD(NS)) · sin(RAD(EW))

其中 NS 是纬度，EW是经度，RAD()用于把角度转成弧度
注意：当坐标在西半球的时候，EW应是负数；当坐标在南半球的时候，NS应是正数。这里必须处理好，否则算出来的坐标不对

读入边的时候计算弧长
因为通过以上计算可以得出两点的直线距离，所以用一下余弦定理就可以算出圆心角，进而算出弧长。之所以用余弦定理而不用其他方法，是因为 arccos() 的值域为 0~2/PI，而 arcsin() 的值域为 -PI/2～PI/2，相对而言arccos不必特判，比较简洁。

上一小段代码（公式已经在草稿纸上化简过，100%的余弦定理）

double distance(int a, int b){
double distLine;
distLine = SQR(coord[a][X]-coord[b][X]) + SQR(coord[a][Y]-coord[b][Y]) + SQR(coord[a][Z]-coord[b][Z]);
return RADIUS * acos(1 - distLine/(2*SQR(RADIUS)));
}

提醒：队列一定要开大一些，一百万会RE，一千万就可以AC

-1

zhengfangyi LV 10 @ 12 年前
为什么不能用Uses math!!!!!!!!!!!!!

歧视么????!!!!

-2

zhujf553 LV 10 @ 12 年前
其实公式不难推，然后用spfa

第9个点死活过不了，只好cheat

-2

小岛 LV 10 @ 12 年前
引用ipip2005“..注意cos函数的单调性，"-pi"?~0单调增，0~pi单调"增"?，分两次二分，求最接近的解..”

....不懂不懂..

我只过了8个点..最后两个点怎么都因为精度问题过不掉.#

-2

FenXy LV 10 @ 12 年前
实践证明一个点的边不到500条.

不usesmath 也能用sin和cos以及arctan的

spfa就行了.数据弱

-2

Cksj LV 8 @ 12 年前
数据过于水货，Dij_Heap ========== 全部 0s

VJ 不让 uses math，但，根本不需要像 ipip2005 做的那么麻烦。直接用 arctan 函数求得球面距离就 ok ！

膜拜吕潇神牛，这题我用 while (not seekeof) 写 32 分，改成 while (not eof) do 就 AC

-2

TLD LV 10 @ 12 年前
我用临接表写的，SPFA一点没优化

太奇怪了，这道题我用流来读入竟然没超时

几何没懂的人，上网查球面三角形

0

naive!! LV 8 @ 2017-12-11 17:53:59

首先这道题似乎用向量点乘不行，精度较低。
还有似乎有些歧义，同一个经纬位置上的点竟然不联通。这个...
以及最后两个点的数据是给满了的，不要侥幸少开。
没错以上就是蒟蒻我提交了几十次的原因QAQ
最后是先转化为直角坐标，两点和球心连成三角形，再用余弦定理求出角度算球面距离。

0

ipip2005 LV 10 @ 2008-11-08 13:19:37

N次提交，终于过了，PASCAL的同志别看题目下面的注释了，Uses math语句，根本不能用，因为禁用的原因，这又是一道语言歧视类题目。

但我是PASCAL的，还是过了此题，在讨论区有我所给出的以知经纬度求球面短弧长的公式，C要过的话直接套用就可以，PASCAL如果要过，就必须用二分！

求出两点关于球心的角度后，本来的下一步是arccos(a) (a)为角度

PASCAL的话要二分a，近似到小数点后七八位左右。

注意cos函数的单调性，-pi~0单调增，0~pi单调增，分两次二分，求最接近的解。

最后提醒一下，SPFA的队列开500万左右才可以，先开100万第9个WA了

-1

Goodhao LV 10 @ 2018-07-04 11:19:47

double get(point a,point b) {
    double dx=abs(a.x-b.x),dy=abs(a.y-b.y);
    return R*2*asin(sqrt(sin(dx/2)*sin(dx/2)+cos(a.x)*cos(b.x)*sin(dy/2)*sin(dy/2)));
}

https://zh.wikipedia.org/wiki/%E5%A4%A7%E5%9C%86%E8%B7%9D%E7%A6%BB
为什么这样会WA啊，这个公式对不对啊

-1

wang_yanheng LV 10 @ 2015-11-22 14:54:58

楼下的是脑抽么!?
用SPFA速度很快，关键在建图。我是这样做的：

读入点的时候计算空间坐标
+ coord[i][Y] = RADIUS · sin(RAD(NS))
+ coord[i][X] = RADIUS · cos(RAD(NS)) · cos(RAD(EW))
+ coord[i][Z] = RADIUS · cos(RAD(NS)) · sin(RAD(EW))

其中 NS 是纬度，EW是经度，RAD()用于把角度转成弧度
注意：当坐标在西半球的时候，EW应是负数；当坐标在南半球的时候，NS应是正数。这里必须处理好，否则算出来的坐标不对

读入边的时候计算弧长
因为通过以上计算可以得出两点的直线距离，所以用一下余弦定理就可以算出圆心角，进而算出弧长。之所以用余弦定理而不用其他方法，是因为 arccos() 的值域为 0~2/PI，而 arcsin() 的值域为 -PI/2～PI/2，相对而言arccos不必特判，比较简洁。

上一小段代码（公式已经在草稿纸上化简过，100%的余弦定理）

double distance(int a, int b){
double distLine;
distLine = SQR(coord[a][X]-coord[b][X]) + SQR(coord[a][Y]-coord[b][Y]) + SQR(coord[a][Z]-coord[b][Z]);
return RADIUS * acos(1 - distLine/(2*SQR(RADIUS)));
}

提醒：队列一定要开大一些，一百万会RE，一千万就可以AC

-1

zhengfangyi LV 10 @ 2009-05-08 17:07:00

为什么不能用Uses math!!!!!!!!!!!!!

歧视么????!!!!

-2

zhujf553 LV 10 @ 2009-10-01 09:11:32

其实公式不难推，然后用spfa

第9个点死活过不了，只好cheat

-2

小岛 LV 10 @ 2009-07-26 08:24:50

引用ipip2005“..注意cos函数的单调性，"-pi"?~0单调增，0~pi单调"增"?，分两次二分，求最接近的解..”

....不懂不懂..

我只过了8个点..最后两个点怎么都因为精度问题过不掉.#

-2

FenXy LV 10 @ 2009-07-18 15:30:04

实践证明一个点的边不到500条.

不usesmath 也能用sin和cos以及arctan的

spfa就行了.数据弱

-2

Cksj LV 8 @ 2009-07-18 13:14:50

数据过于水货，Dij_Heap ========== 全部 0s

VJ 不让 uses math，但，根本不需要像 ipip2005 做的那么麻烦。直接用 arctan 函数求得球面距离就 ok ！

膜拜吕潇神牛，这题我用 while (not seekeof) 写 32 分，改成 while (not eof) do 就 AC

-2

TLD LV 10 @ 2009-03-16 23:01:41

我用临接表写的，SPFA一点没优化

太奇怪了，这道题我用流来读入竟然没超时

几何没懂的人，上网查球面三角形

-2

biran007 LV 6 @ 2009-03-02 18:57:42

这题觉得有点不合理

按常识，同经纬度的点应当看成连通的，东经180和西经180应该等价，北（南）纬90度的点只有一个

这么考虑的话反而有3个点过不了……

-2

~笨小孩不笨~ LV 3 @ 2008-11-22 11:47:58

问个问题

圣诞老人是从地下直线穿越还是绕地球表面走的？

还有数据范围用floyd是不是会爆

-2

鸟山明 LV 5 @ 2007-06-01 19:28:56

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：160ms

嗯..速度果然很快..

这个题真综合性真是强啊,地理,立体几何,数据结构(就是HEAP啦),图论算法,全齐了.

本人才初三,搞那个立体的计算几何很不容易的,辛苦.

第一次写DIJKSTRA+HEAP,练习一下,成功

但是居然神奇地一次提交就过了,其实很成功的,但是实在是感觉没有成就感,因为没有WA很多次经过不懈努力才AC的爽的感觉...那个才叫爽,才叫释放

-3

mike_nzk LV 10 @ 2009-10-31 15:12:35

由于比赛，竟然running了一次，浪费一次提交！！！

注意精度，arccos函数注意边界（特殊值）处理。

-3

Bobby_Z LV 7 @ 2008-09-22 20:02:49

其实很简单的。。

-3

188513911 LV 9 @ 2008-07-21 19:04:01

忘删调试语句，24分，全Impossibe

删了........AC!!!

555555555555~~~~~~~~~~~~~

白交一次!!!

-3

AlNo3 LV 9 @ 2008-07-15 09:54:11

忠告！！！！

千万不要用SeekEof！！！！

-3

asd4823765 LV 9 @ 2007-11-17 09:56:02

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 1ms

├ 测试数据 10：答案正确... 1ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2ms

有点慢啊`\`\`

题解

23 条题解

送给圣诞夜的行程

信息

状态

开发

支持

题解

23 条题解

送给圣诞夜的行程

信息

状态

开发

支持

还没有账户？

登录