| 题目名称 | 2008. [USACO Dec08] 巨大的围栏 |
|---|---|
| 输入输出 | fence1.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2015-06-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：31， 提交：51， 通过率：60.78% | ||||
 张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.258 s | 1.69 MiB | C++ |
 FoolMike |
100 | 0.333 s | 2.13 MiB | C++ |
|
mikumikumi |
100 | 0.348 s | 1.35 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.360 s | 1.27 MiB | C++ |
 阿狸 |
100 | 0.406 s | 1.75 MiB | C++ |
 CYY |
100 | 0.438 s | 1.31 MiB | C++ |
 一個人的雨 |
100 | 0.526 s | 1.69 MiB | C++ |
 0 |
100 | 0.686 s | 2.35 MiB | C++ |
 000 |
100 | 0.786 s | 2.43 MiB | C++ |
|
000 |
100 | 0.820 s | 2.89 MiB | C++ |
| 关于 巨大的围栏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @cstdio :
真是好题，Orz萌帝！ FoolMike
2017-06-05 17:01
4楼
| ||||
|
同样是n^3的做法，为什么差别这么大？
| ||||
|
貌似如果数据是一个标准的矩形，就会被卡掉。。。。。 $\sum poet$
 stone
2016-04-05 14:18
2楼
| ||||
|
感觉USACO的题普遍比CF的漂亮啊……
解题报告：http://blog.csdn.net/wmdcstdio/article/details/46695233 | ||||
神利·代目
cstdio【题目描述】
Farmer John的农场里有$N（5<=N<=250）$个篱笆桩，每个都有独一无二的坐标$(x_i,y_i)（1<=x_i,y_i<=1000）$。他想选择尽量多的篱笆桩来构建他的围栏。这个围栏要美观，所以必须是凸多边形的。那他最多能选多少个呢？
所有的篱笆桩中不存在三点共线。
【输入格式】
第1行输入N，之后N行一行输入一个坐标。
【输出格式】
一行一个正整数，最多能选多少个。
【样例输入】
6
5 5
2 3
3 2
1 5
5 1
1 1
【样例输出】
5
【提示】
选择的5个篱笆桩分别是$(2,3),(3,2),(5,1),(5,5),(1,5)。$
【来源】
Zoran Dzunic,2008
译者：BirDOR