Skip to content

11303: 【原1303】保护Taring

题目

题目描述

author: were 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1303

Description

时间限制:0.5s 空间限制:64MB

Taring出了好多不河蟹的题目,要被同学们阿鲁巴了。

面临这一危机,Taring的好队友were决心帮助他,延缓他被阿鲁巴的时间。

were在平面上设立了好多木桩,然后可以在两个木桩之间架设篱笆,

一个木桩上最多架设两段篱笆。

were架设了若干层封闭的篱笆,然后把Taring藏在了最里面的一层。

一群刚刚被Taring的题目凌虐过的同学们突破一层封闭的篱笆需要一个单位的时间,

现在问题来了:were最多能架设多少层封闭的篱笆,以使得延缓Taring被阿鲁巴的时间最长。

Input Format

输入共有N+1行。

第1行有1个整数,表示地面上有多少个木桩。

第2..N+1行有每行有一对整数,表示木桩的位置。

Output Format

输出共一个整数,表示对Taring进行阿鲁巴这一活动最多能被延缓多久。

Sample Input

8
0 0
8 0
8 3
0 3
2 1
2 2
3 2
3 1

Sample Output

2

Data Range

对于10%的数据,N<=10。

对于100%的数据,N<=2000,|xi,yi|<=100000。

鉴于前面几次机考总是有人写十个点各1s的暴力,为了节约大家反复提交进行评测的时间,特此0.5s。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!