P1863 独眼兔

    • 33通过
    • 122提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 计算几何 NOI导刊
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    太郎有一只特殊的兔子,它只有一只左眼,所以当它移动时是不能向右转弯的。一天,太郎跟独眼兔做一个游戏,太郎在平面内放了N个萝卜,每个萝卜有个位置(xi,yi),且任意两个萝卜的xi,yi都是不相同的,独眼兔要去吃这些萝卜。设萝卜A(xi,yi)是所有萝卜中最小的,那独眼兔会从(0,yi)出发,走向萝卜A,然后开始吃萝卜。当它吃完一个萝卜后,独眼兔会确定下一个萝卜作为目标,然后径直向萝卜走去,当然当它移动的时候是不能向右转弯的。独眼兔还有一个特点,它走过的路径上会留下特殊的气味,所以独眼兔不希望它将要走的路与前面它走过的路相交。太郎想知道独眼兔如何才能吃到最多的萝卜。

    输入输出格式

    输入格式:

    第一行是个整数N;

    接下来N行,每行两个整数。第i+1行表示第i号萝卜的位置(xi,yi)。

    输出格式:

    一行,输出最多能吃到的萝卜数,后面输出吃萝卜的顺序。

    输入输出样例

    输入样例#1: 复制
    10
    4 5
    9 8
    5 9
    1 7
    3 2
    6 3
    10 10
    8 1
    2 4
    7 6
    
    输出样例#1: 复制
    10 8 7 3 4 9 5 6 2 1 10

    说明

    40%的数据,n≤100;

    100%的数据,n≤1000;0<xi≤10000;0<yi≤10000。

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