#P1309. [POI2005]Pra-Dextrogyrate camel

    ID: 249 传统题 1000ms 512MiB 尝试: 47 已通过: 26 难度: 8 上传者: 标签>CF2500省选/NOI-线性 DP自定义排序规则叉积二分查找普通线段树环形区间拆分

[POI2005]Pra-Dextrogyrate camel

题目描述

霸中由沙漠中的 nn 个绿洲组成,没有三个绿洲是共线的。DYY 住在其中的一个绿洲中,而他在每个绿洲里都有一个朋友。

DYY 想骑骆驼出去旅行一趟,拜访尽量多的朋友。这只骆驼非常固执,它只以它独特的方式前进:

  • 离开一个绿洲后,它只沿一条直线前进,直到它到达另一个绿洲;
  • 它只在绿洲里转弯,但它只朝右转(顺时针),并且角度在[0°,180°][0 \degree,180 \degree]内(它在一个绿洲只做一次转弯,也就是说,它不会转 200°=100°+100°200 \degree=100 \degree+100 \degree);
  • 它的路线不会交叉,也就是说,它不会经过任何一个点两次(除了出发点之外)。

请你帮助 DYY 设计一条路线,让他能访问尽量多的朋友。这条路线必须从 DYY 住的绿洲出发,最后回到原处。

输入格式

第一行一个正整数 n(3≤n≤1000)n(3\leq n\leq 1000) 表示绿洲的个数。 接下来第 i+1i + 1 行两个数 (xi,yi)(x_{i}, y_{i}) 描述第 ii 个绿洲的坐标,xi,yi∈[−16000,16000]x_{i}, y_{i} \in [-16000,16000]。

输出格式

一行,输出最多能访问的朋友的个数。

样例输入

6
1 1
-1 4
0 -1
4 1
0 3
1 4

样例输出

4

样例说明

DDY 最初在绿洲 11,他的骆驼首先面朝绿洲 22。

数据规模与约定

对于 30%30\% 的数据,n≤20n\leq 20; 对于 60%60\% 的数据,n≤200n\leq 200; 对于 100%100\% 的数据,n≤1000n\leq 1000。

原始题意补充

以下是所有测试数据均采用的初始条件,并非只对样例有效:旅行者住在编号1的绿洲,骆驼一开始朝向编号2的绿洲,并且必须沿1到2作为第一段。返回绿洲1之后的朝向不受限制。旅行者只在其他绿洲有朋友,答案不包含起点1。

本站当前数据版本的可行性保证

本站当前全部10个原测试文件均已通过整数叉积核验:至少存在一个编号v不小于3的绿洲,位于有向线段1到2的严格右侧,即

(x2−x1)(yv−y1)−(y2−y1)(xv−x1)<0.(x_2-x_1)(y_v-y_1)-(y_2-y_1)(x_v-x_1)<0.

因此1到2到v再回到1是一条简单的顺时针三角形路线,满足所有转弯和不重复经过位置的要求,至少可以访问两位朋友。当前教学版本明确保证存在这样的v,所以一定存在合法旅行路线。

这项可行性条件是本站当前数据版本的明示补充,不冒称原官方文字已经给出。原存档没有定义不存在合法路线时的输出,本版本不接收这类输入,也不擅自赋予其0或-1作为答案。