| 题目名称 | 579. 打蚊子 |
|---|---|
| 输入输出 | fight.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2011-07-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：28， 通过率：21.43% | ||||
 ztx |
100 | 1.147 s | 0.32 MiB | C++ |
 苏轼 |
100 | 1.914 s | 0.30 MiB | C++ |
 PurpleShadow |
100 | 1.991 s | 0.29 MiB | C++ |
|
PurpleShadow |
100 | 2.109 s | 0.34 MiB | C++ |
|
PurpleShadow |
100 | 2.177 s | 0.34 MiB | C++ |
 天一阁 |
100 | 2.365 s | 0.51 MiB | C++ |
|
ztx |
90 | 2.185 s | 0.32 MiB | C++ |
|
PurpleShadow |
90 | 2.209 s | 0.34 MiB | C++ |
|
ztx |
90 | 2.490 s | 0.32 MiB | C++ |
|
天一阁 |
90 | 3.233 s | 0.51 MiB | C++ |
| 本题关联比赛 | |||
| 20110728 | |||
| 关于 打蚊子 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
抱歉我只会O(nlogn)~O(nsqrt(n))暴力
 | ||||
|
法一：O(n3)过五组，剩下超时
法二：O(n2)过三组，剩下错误 求先进流解题法 | ||||
Truth.Cirno题目描述
输入文件 fight.in
输出文件 fight.out
TB晚上痒得睡不着觉，向墙上一看才发现墙上有N只大蚊子！为了报这笔血海深仇，TB悄悄地拿起电蚊拍。
电蚊拍可以近似看成一个半径为R的圆形，只要接触到这个圆形的边界或内部，蚊子就会被电死。TB知道，尽管剩下的蚊子都会很生气，但由于难兄难弟们被电发出的噼里啪啦的声音，这些剩下的蚊子肯定会应声逃跑，所以机会只有一次。你能告诉TB，这样一个圆形的电蚊拍一次最多能打死多少蚊子吗？
输入格式：
第一行两个整数N、R分别表示蚊子的个数以及电蚊拍的半径。
接下来N行，每行两个整数X、Y表示蚊子的横坐标和纵坐标。
输出格式：
一个整数，表示最多打死蚊子的数量。
输入样例
4 1
0 0
2 0
1 1
1 2
输出样例：
3
数据规模：
X、Y、R<=2^16
|
测试点 |
N |
备注 |
|
1~3 |
≤500 |
|
|
4 |
≤1000 |
|
|
5 |
≤2000 |
R=1 |
|
6~10 |
≤2000 |
|