P2526 [SHOI2001]小狗散步

    • 476通过
    • 1K提交
  • 题目提供者 谁懂谁伤心
  • 评测方式 云端评测
  • 标签 各省省选 2001(或之前) 上海 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Grant喜欢带着他的小狗Pandog散步。Grant以一定的速度沿着固定路线走,该路线可能自交。Pandog喜欢游览沿途的景点,不过会在给定的N个点和主人相遇。小狗和主人同时从(X1,Y1)点出发,并同时在(Xn,Yn)点汇合。小狗的速度最快是Grant的两倍。当主人从一个点以直线走向另一个点时,Pandog跑向一个它感兴趣的景点。Pandog每次与主人相遇之前最多只去一个景点。

    题目描述

    你现在的任务是:为Pandog寻找一条路线(有可能与主人的路线部分相同),使它能够游览最多的景点,并能够准时与主人在给定地点相遇或者汇合。

    输入输出格式

    输入格式:

    输入文件第一行是两个整数N和M( 1≤N,M≤100 );

    输入文件第二行的N个坐标给出了Grant的散步路线,即Pandog和主人相遇地点;

    输入文件第三行的M个坐标给出了所有Pandog感兴趣的景点。

    所有输入的坐标均不相同,且绝对值不超过1000。

    输出格式:

    输出小狗的移动路线。

    第一行是经过的点数,第二行依次为经过的点的坐标(直角坐标系)

    输入输出样例

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

    说明

    "The way is wrong!"表示输出方案错误(可能是坐标不存在输入文件中,两个相遇点间存在多个景点,或距离超出范围)

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