P3493 [POI2009]WSP-Island

    • 51通过
    • 117提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 半平面相交,半平面交 计算几何 POI 2009 Special Judge 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Byteasar is the king of Byteotia, an island in The Ocean of Happiness.

    The island is a convex shape, and all the towns of Byteotia are located on the shore.

    One of these towns is Byteburg, the famous capital of Byteotia.

    Every pair of towns is connected by a road that goes along the line segment between the towns.

    Some roads that connect different pairs of towns intersect - there is a crossroad at each such intersection.

    Bitratio, Byteasar's rival to the throne, had hatched a sordid plot.

    While Byteasar was travelling from the capital to an adjacent town, Bitratio's people seized Byteburg.

    Now Byteasar has to return to Byteburg as soon as possible in order to restore his rule.

    Unfortunately, some of the roads are controlled by Bitratio's guerrilla.

    Byteasar cannot risk the use of such roads, he can however cross them at the crossroads.

    Needless to say, he has to travel along the roads and hence turn only at the crossroads, for otherwise the journey would take far too long.

    Byteasar's loyal servants have informed him which roads are safe.

    Byteasar believes your loyalty, and thus entrusts you with a task to find the shortest safe route from the town he is currently in to Byteburg.

    Byteotia岛屿是一个凸多边形。城市全都在海岸上。按顺时针编号1到n。任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。有一些道路被游击队控制了,不能走,但是可以经过这条道路与未被控制的道路的交点。问从城市1到n的最短距离。

    输入输出格式

    输入格式:

    In the first line of the standard input two integers and are given (, ), separated by a single space, that denote respectively: the number of towns and the number of roads controlled by Bitratio's guerrilla.

    Let us number the towns from to starting from Byteburg and moving clockwise along the shore.

    Bytesar is currently in the town no. .

    Each of the following lines holds a pair of integers and (![](http://main.edu.pl/images/O

    输出格式:

    Your programme is to print out one floating point number to the standard output:

    the length of the shortest safe route leading from the town no. to Byteburg.

    The absolute difference between the number returned and the correct one has to be at most .

    输入输出样例

    输入样例#1: 复制
    6 9
    -12 -10
    -11 6
    -4 12
    6 14
    16 6
    18 -2
    3 4
    1 5
    2 6
    2 3
    4 5
    3 5
    1 3
    3 6
    1 6
    
    输出样例#1: 复制
    42.0000000000
    

    说明

    spj-

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