POJ-Radar Installation-欲張り-区間選点
1624 ワード
n個の島の座標を与え,dを与え,X軸に取り付けられたレーダーの小半径を示す
少なくとも何個のレーダーを積んですべての島を覆うことができますか?
明らかに1つの島のyがdより大きいのは無解の案で、出力-1
残りの状況は実は 【区間選点】問題は同じです
各島に対応する区間【a,b】は、この区間にレーダーが取り付けられ、島が覆われることを示す
n区間、どのように点を選んで点を最小にして、各区間に少なくとも1つの点が存在して、これは【区間選点】の問題です
区間のb(右端点)を昇順に並べ替え、bは同じa昇順に並べ替える
1つ目から選択し、1つ目の区間に1つの点を記入し、できるだけ多くの区間をカバーさせるには、明らかに「区間の右端点」に点を記入するのが最適であり、他のより良い案は存在しない.
したがって、次の区間の左端点がこの右端点以下であると、すでに上書きされ、
【1つの区間の左端点が前に記入した点より大きいまで】この場合、もう1つの点を記入する必要があることを示します.のこの手順を全区間で考慮するまで繰り返します
答えだよ
少なくとも何個のレーダーを積んですべての島を覆うことができますか?
明らかに1つの島のyがdより大きいのは無解の案で、出力-1
残りの状況は実は 【区間選点】問題は同じです
各島に対応する区間【a,b】は、この区間にレーダーが取り付けられ、島が覆われることを示す
n区間、どのように点を選んで点を最小にして、各区間に少なくとも1つの点が存在して、これは【区間選点】の問題です
区間のb(右端点)を昇順に並べ替え、bは同じa昇順に並べ替える
1つ目から選択し、1つ目の区間に1つの点を記入し、できるだけ多くの区間をカバーさせるには、明らかに「区間の右端点」に点を記入するのが最適であり、他のより良い案は存在しない.
したがって、次の区間の左端点がこの右端点以下であると、すでに上書きされ、
【1つの区間の左端点が前に記入した点より大きいまで】この場合、もう1つの点を記入する必要があることを示します.のこの手順を全区間で考慮するまで繰り返します
答えだよ
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
struct node
{
double x,y;
};
node tm[1005];
int cmp(node a,node b)
{
if (a.y!=b.y)
return a.y<b.y;
else
return a.x<b.x;
}
double inf = 2147483647;
int main()
{
int i;
int n,d;
int cnt=1;
while(cin>>n>>d)
{
if (!n&&!d) break;
int x,y;
int flag=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if (abs(y)>d)
flag=1;
double dis ;
dis=sqrt((double)(d*d-y*y));
tm[i].x=x-dis;
tm[i].y=x+dis;
}
if (flag)
{
printf("Case %d: %d
",cnt++,-1);
continue;
}
sort(tm+1,tm+1+n,cmp);
int ans=0;
double start=-inf;
for(i=1;i<=n;i++)
{
if (tm[i].x>start)
{
start=tm[i].y;
ans++;
}
else
continue;
}
printf("Case %d: %d
",cnt++,ans);
}
return 0;
}