| 题目名称 | 1454. [USACO Nov13]视线 |
|---|---|
| 输入输出 | sight.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 11 |
| 题目来源 |
 cqw
于2013-12-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：33， 通过率：45.45% | ||||
 策 |
100 | 0.097 s | 2.83 MiB | C++ |
 Bennettz |
100 | 0.107 s | 0.37 MiB | C++ |
 cstdio |
100 | 0.162 s | 0.31 MiB | C++ |
 kxxy |
100 | 0.172 s | 0.31 MiB | C++ |
 _Horizon |
100 | 0.178 s | 2.65 MiB | C++ |
 _stranger |
100 | 0.190 s | 0.31 MiB | C++ |
 stone |
100 | 0.193 s | 1.69 MiB | C++ |
|
kxxy |
100 | 0.207 s | 0.31 MiB | C++ |
 mouse |
100 | 0.238 s | 0.31 MiB | C++ |
 zhengtn03 |
100 | 0.294 s | 1.48 MiB | C++ |
| 本题关联比赛 | |||
| 20131207 | |||
| 关于 视线 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Chenyao :
不用切线，用切点的角度表示 | ||||
|
回复 @mouse :
突然想起来可以用堆替代平衡树，可是之后怎么写？  Chenyao2333
2013-12-14 13:53
5楼
| ||||
|
若“看不见”，则此点对应两切点在另一个点对应两切点所成优弧上。
一个误把下标从1开始的程序居然过了十个点…… | ||||
|
回复 @mouse : 咋写
 C语言入门
2013-12-11 20:59
3楼
| ||||
|
有
mouse
2013-12-09 19:22
2楼
| ||||
|
两个看不见的时候必定可以找到两条平行切线，使两牛在平行线中
把所有切线的斜率求出来，然后排序，上平衡树扫描 求神犇，有没有不这么丧心病狂简单些的解法？ Chenyao2333
2013-12-08 10:47
1楼
| ||||
【题目描述】
FJ的N（1<=N<=50,000）头牛被安置在他的二维平面牧场上互不相同的点上，在牧场中央是一个大的圆形谷仓，处于谷仓两边相对位置的牛无法看到彼此，因为视线会被谷仓遮挡。请计算借由直线视线能看到彼此的牛的对数。
谷仓的中心点坐标为（0,0），半径为R，谷仓所处的圆的边线及圆内均没有牛，任意两头牛都不会同时处于圆的某条切线上。R的取值为1～1,000,000，每头牛的位置坐标均为-1,000,000～+1,000,000的整数。
【输入格式】
第1行：两个整数N，R；
第2～N+1行：每行有两个整数，表示一头牛的位置坐标。
【输出格式】
一行，即能互相看到的牛的对数。
【样例输入】
4 5 0 10 0 -10 10 0 -10 0
【样例输出】
4 输出解释： 在所有牛的6对组合中，只有两对是互相看不到的，分别是坐标为(-10,0)和(10,0)的，以及坐标为(0,10)和(0,-10)的。
【提示】
在此键入。
【来源】
USACO 2013 November Contest, Gold