P3340 [ZJOI2014]星系调查

    • 35通过
    • 92提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2014 浙江 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    银河历59451年,在银河系有许许多多已被人类殖民的星系。如果想要在行星系间往来,大家一般使用连接两个行星系的跳跃星门。 一个跳跃星门可以把物质在它所连接的两个行星系中互相传送。露露、花花和萱萱被银河系星际联盟调查局任命调查商业巨擘ZeusLeague+的不正当商业行为。

    在银河系有N个已被ZeusLeague+成功打入市场的行星系,不妨标号为1,2,...,N。而ZeusLeague+在这N个行星系之间还拥有自己的M个跳跃星门。使用这些跳跃星门,ZeusLeague+的物资就可以在这N个行星系中两两任意互相传输。由于经费问题,跳跃星门的个数不会超过行星系的个数。

    露露在颇费周折之后得到了ZeusLeague+在这N个行星系中的各自的贸易总额C[i]。

    萱萱设计了一个经济学特征指标D[i]来度量这N个行星系的经济学特征。于是,我们可以用二元组(C[i],D[i])来表示第i个行星系的XP(Xuan's Position)。现在假设我们有k个行星系的XPs,把它们放置在二维平面上,然后我们用一条直线去拟合这些XPs。定义一条直线与XPs的相斥度为这条直线到各个XP的Euclid距离的平方之和。再令XPs的线性假设相斥度为所有直线与XPs的相斥度中的最小者。那么,这个值越小,ZeusLeague+在这k个行星系中的相互贸易活动就越可疑,从而值得进一步调查。花花负责计算许多行星系对(u,v)的非可疑度。一条跳跃星门航线的非可疑度被定义为它经过的所有行星系(包括起点和终点)的XPs的线性假设相斥度。而一个行星系对(u,v)的非可疑度则被定义为所有以u为起点,v为终点的跳跃星门航线的非可疑度中的最小值。一条跳跃星门航线是指从某个行星系开始,通过跳跃星门依次到达某些行星系,然后终止,并且中途不重复经过行星系,这样的一个过程。

    花花负责计算许多行星系对(u,v)的非可疑度。一条跳跃星门航线的非可疑度被定义为它经过的所有行星系(包括起点和终点)的XPs的线性假设相斥度。而一个行星系对(u,v)的非可疑度则被定义为所有以u为起点,v为终点的跳跃星门航线的非可疑度中的最小值。一条跳跃星门航线是指从某个行星系开始,通过跳跃星门依次到达某些行星系,然后终止,并且中途不重复经过行星系,这样的一个过程。

    在花花数天夜以继日的工作之后,平行调查组的你——大名鼎鼎的计算机科学家Hcceleration.Gerk.Gounce不忍心看到她这样不眠不休,于是你在完成了手头的工作之后决定帮一帮她。

    输入输出格式

    输入格式:

    第一行是N,M,分别表示这个银河系内的行星系的个数以及跳跃星门的个数。接下来N行,每行2个正整数C[i], D[i],表示第i 个行星系的XP(Xuan's Position)。接下来的M行来描述跳跃星门,每行2个正整数u[i],v[i],表示有一个连接着行星系u[i]和v[i]的跳跃星门。注意这个连接是无向的。不会存在自己连向自己的情况。也不会存在重复连接的情况。接下来的一行,有一个正整数Q,表示花花需要计算的非可疑度的行星对数。接下来的Q行,每行2个正整数s[i], t[i],表示花花需要计算从s[i]到t[i]的非可疑度。

    输出格式:

    总共Q行,每一行一个实数,表示花花第i次需要计算的答案。你的答案需要和标准答案的差不超过0.01才能得分。

    输入输出样例

    输入样例#1: 复制
    6 6
    3 4
    5 6
    1 3
    4 4
    3 3
    2 4
    1 2
    1 3
    2 3
    2 4
    3 5
    5 6
    3
    3 6
    2 4
    4 6
    输出样例#1: 复制
    0.66667 
    0.00000 
    1.67544

    说明

    [spj 0.01]

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。