P3433 [POI2005]PRA-Dextrogyrate Camel

    • 1通过
    • 2提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 POI 2015 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    征求翻译。如果你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。

    题目描述

    Byteotia consists of $N$ oasis in the desert, no three of which are collinear. Byteasar lives in one of these oasis and moreover he has an acquaintance in every other. Byteasar wants to pay a visit to as many of them as possible. He plans to travel on the back of his camel. The camel is as obstinate as a mule and thus moves in its own peculiar way:

    After departure from an oasis it moves along a straight line, until it gets to another oasis.

    The camel turns only at oasis, but it turns only right (clockwise) and by an angle from the interval $[0\degree,180\degree]$ (the camel makes only one turn at an oasis, i.e. it will not turn by f.i. $200\degree$ as a result of two subsequent turns by $100\degree$).

    The camel doesn't want to follow its own footprints.

    Help Byteasar in planning such a route that he will be able to visit as many friends as possible. It should both begin and end in the oasis where Byteasar lives. It has to consist of segments connecting subsequently visited oasis. The route may not pass through any point two times, except the Byteasar's oasis, where the camel turns up twice: at the beginning and the end of the journey.

    Byteasar's camel is initially facing a certain oasis and it has to start moving toward it. The direction the camel faces after returning from the journey is of no importance.

    TaskWrite a programme that:

    reads from the standard input the camel's coordinates and the direction it faces as well as the coordinates of the Byteotian oasis,determines the maximum number of friends Byteasar can pay a visit to while sticking to the presented rules,writes the result to the standard output.

    Byteotia大陆由沙漠中的N个绿洲组成,没有三个绿洲是共线的。Byteasar住在其中的一个绿洲中,而他在每个绿洲里都有一个朋♂友。Byteasar想骑羊驼出去旅行一趟,拜访尽量多的朋友。这只羊驼非常固执,它只以它独特的方式前进: 离开一个绿洲后,它只沿一条直线前进,直到它到达另一个绿洲; 它只在绿洲里转弯,但它只朝右转(顺时针),并且角度在[0°,180°]内(它在一个绿洲只做一次转弯,也就是说,它不会转超过180°);它的路线不会交叉,也就是说,它不会经过任何一个点两次(除了出发点)。 请你帮助Byteasar(的羊驼)设计一条路线,让他能访问尽量多的朋♂友。这条路线必须从Byteasar住的绿洲出发,最后回到原处。Byteasar最初在绿洲1,他的骆驼首先面朝绿洲2

    输入输出格式

    输入格式:

    In the first line of the standard input there is one integer $N$ ($3\le N\le 1\ 000$) - the number of oasis in Byteotia. The oasis are numbered from $1$ to $N$. Byteasar lives in the oasis no. $1$ and his camel is facing the oasis no. $2$. In the following $N$ lines the coordinates of the oasis are given. In the $(i+1)$'th line there are two integers $x_i$, $y_i$ - the horizontal and vertical coordinate of the $i$'th oasis - separated by a single space. All coordinates are from the interval from $-16\ 000$ to $16\ 000$.

    第一行,输入一个整数N(3≤N≤1,000)代表Byteotia大陆中的绿洲数。

    绿洲被从1到N编号,Byteasar住在1号绿洲,而他的羊驼面向2号绿洲。

    接下来的N行输入,第(i+1)行有两个整数xi,yi(-16,000≤xi,yi≤16,000)代表i号绿洲的横纵坐标,他们之间被一个空格隔开。

    输出格式:

    In the first and only line of the standard output your programme should write one integer - the maximum number of friends Byteasar can visit.

    只有一行输出,即Byteasar能拜访的最多的好♂友数量。

    输入输出样例

    输入样例#1: 复制
    6
    1 1
    -1 4
    0 -1
    4 1
    0 3
    1 4
    输出样例#1: 复制
    4

    说明

    样例解释:

    感谢@Paperback_Writer 提供翻译

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