uva live 7635 National Bomb Defusing Squad

妖狐艹你老母 2021-09-20 10:00 140阅读 0赞

题目链接：[https://icpcarchive.ecs.baylor.edu/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=5657][https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_5657]

# 题意： #

有n个人，每一个人都可能携带boom，给出你这些人的位置x, y。 q次询问， 每次给你一个R（爆炸范围），求能炸到多少个人的期望。

# 题解： #

A到B的距离与B到A的距离相同，我们只需要将每2个人的距离算出来，排序，每给出一个R ，就找小于R 的数量 \* 2 ， 最后还要加上自己死亡 n 。

记得case完要空行

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <string>
     5 #include <algorithm>
     6 #include <cmath>
     7 #include <vector>
     8 #include <queue>
     9 #include <map>
    10 #include <stack>
    11 #include <set>
    12 using namespace std;
    13 typedef long long LL;
    14 typedef unsigned long long uLL;
    15 #define ms(a, b) memset(a, b, sizeof(a))
    16 #define pb push_back
    17 #define mp make_pair
    18 #define eps 0.0000000001
    19 #define IOS ios::sync_with_stdio(0);cin.tie(0);
    20 const LL INF = 0x3f3f3f3f3f3f3f3f;
    21 const int inf = 0x3f3f3f3f;
    22 const int mod = 1e9+7;
    23 const int maxn = 3000+10;
    24 int x[maxn], y[maxn];
    25 int dis[maxn*maxn];
    26 int n, q, r;
    27 int cul(int i, int j)
    28 {
    29     return (y[j]-y[i])*(y[j]-y[i])+(x[j]-x[i])*(x[j]-x[i]);
    30 }
    31 void solve()
    32 {
    33     int cnt = 0;
    34     for(int i = 0;i<n;i++)  scanf("%d%d", &x[i], &y[i]);
    35     for(int i = 0;i+1<n;i++){
    36         for(int j = i+1;j<n;j++){
    37             dis[cnt++] = cul(i, j);
    38         }
    39     }
    40     sort(dis, dis+cnt);
    41     int ans;
    42     while(q--){
    43         scanf("%d", &r);
    44         int pos = upper_bound(dis, dis+cnt, r*r) - dis;
    45         ans = 0;
    46         ans += 2*pos;
    47         ans += n;
    48         printf("%.2f\n", (double)ans/(double)n);
    49     }
    50     printf("\n");
    51 }
    52 int main() {
    53 #ifdef LOCAL
    54     freopen("input.txt", "r", stdin);
    55 //        freopen("output.txt", "w", stdout);
    56 #endif
    57 //    IOS
    58     while(~scanf("%d%d", &n, &q)&&n+q){
    59         solve();
    60     }
    61     return 0;
    62 }

uva的评测机很慢，居然不能用二维来算，然后排序， 有点卡常。

转载于:https://www.cnblogs.com/denghaiquan/p/7287996.html

[https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_5657]: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5657
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210726/29909eeca1e24881b7680ba45c14fab4.png