首页 > 代码库 > LightOj1383 - Underwater Snipers（贪心 + 二分）

LightOj1383 - Underwater Snipers（贪心 + 二分）

2024-08-14 05:25:42   218人阅读

题目链接：http://lightoj.com/volume_showproblem.php?problem=1383

题意：在平面图中，有一条河，用直线y=k表示，河上面(y>k)的都是敌方区域，y<k的都是水，现在有s个狙击手在水中不知道他们的位置；有n个敌军的士兵，已知他们的坐标；

狙击手有一个射击的范围 D，现在要满足所有敌方士兵都在狙击手的射击范围内，而且还要离河的距离M尽量的远，其中M是所有狙击手离河的距离最近的那个；如果不能满足输出“impossible”

距离最大化，我们可以二分，对于给定的一个距离d，看s个点是否能包含n个点即可；怎么判断就是相当于poj的一道雷达的那题，用贪心即可；

 

技术分享
#include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<set>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define maxn 10005#define maxm 20005#define INF 0x3f3f3f3ftypedef long long LL;struct node{    int x, y;    double L, R;}a[maxn], b[maxn];int n, s, k, D;int cmp(node p, node q){    if(p.R != q.R)        return p.R < q.R;    return p.L < q.L;}bool Judge(int d){    for(int i=1; i<=n; i++)    {        if(a[i].y + d > D)            return false;    }    met(b, 0);    for(int i=1; i<=n; i++)    {        double y = a[i].y + d*1.0;        double x = sqrt(1.0*D*D - y*y);        b[i].L = a[i].x - x;        b[i].R = a[i].x + x;    }    sort(b+1, b+n+1, cmp);    int ans = 1;    double R = b[1].R;    for(int i=2; i<=n; i++)    {        if(b[i].L > R)        {            ans ++;            R = b[i].R;        }    }    return ans <= s;}int main(){    int T, t = 1;    scanf("%d", &T);    while(T--)    {        scanf("%d %d %d %d", &k, &n, &s, &D);        for(int i=1; i<=n; i++)        {            scanf("%d %d", &a[i].x, &a[i].y);            a[i].y -= k;        }        int L = 1, R = D, ans = -1;        while(L <= R)        {            int Mid = (L+R)/2;            if(Judge(Mid))            {                ans = Mid;                L = Mid + 1;            }            else                R = Mid - 1;        }        printf("Case %d: ", t++);        if(ans == -1)            puts("impossible");        else            printf("%d\n", ans);    }    return 0;}
View Code

 

LightOj1383 - Underwater Snipers（贪心 + 二分）


联系
我们