http://poj.org/problem?id=1328
X軸的上方代表海，下方代表陸地。海中有多個島嶼，X軸上可任意放置半徑為d的雷達，求至少放置多少個雷達可覆蓋所有島嶼，不能完成輸出－1。
?? ?以島嶼為圓心做半徑為d的圓，可在X軸上產生兩個交點，即為X軸上可覆蓋該島嶼的區(qū)間，求出所有島嶼所對應的區(qū)間，將交集不為空的區(qū)間分為一組，這樣你會發(fā)現(xiàn)答案其實就是求區(qū)間可分為多少組。
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
struct point
{
?? ? ? double x,y;
}p[1005];
struct in
{
?? ? ?double l,r;
}q[1005];
int cmp(in a,in b)
{
?? ?if(a.l-b.l<-1e-8)
?? ?return 1;
?? ?else
?? ?return 0;
}
double dis(point a,point b)
{
?? ? ? return sqrt(a.x*a.x+b.y*b.y);
}
int main()
{
?? ?int i,j,ans,n,d,flag,cas=1;
?? ?double x,a,b;
?? ?while(scanf("%d%d",&n,&d),n+d)
?? ?{
?? ? ? ? flag=0;ans=1;
?? ? ? ? for(i=0;i<n;i++)
?? ? ? ? {
?? ? ? ? ? ? ?scanf("%lf%lf",&p[i].x,&p[i].y);
?? ? ? ? ? ? ?if(p[i].y>d)
?? ? ? ? ? ? ?flag=1;
?? ? ? ? }
?? ? ? ? if(flag)
?? ? ? ? {
?? ? ? ? ? ? ?printf("Case %d: -1\n",cas++);
?? ? ? ? ? ? ?continue;
?? ? ? ? }
?? ? ? ? for(i=0;i<n;i++)
?? ? ? ? {
?? ? ? ? ? ? ?q[i].l=p[i].x-sqrt(d*d-p[i].y*p[i].y);
?? ? ? ? ? ? ?q[i].r=sqrt(d*d-p[i].y*p[i].y)+p[i].x;
?? ? ? ? } ? ? ? ? ? //求解每個區(qū)間。
?? ? ? ? sort(q,q+n,cmp); ? //每個區(qū)間以左端點大小，從小到大排序。
?? ? ? ? a=q[0].l;b=q[0].r;
?? ? ? ? for(i=1;i<n;i++)
?? ? ? ? {
?? ? ? ? ? ? ?if(q[i].l>b)
?? ? ? ? ? ? ?{
?? ? ? ? ? ? ? ? ? ans++;
?? ? ? ? ? ? ? ? ? a=q[i].l;
?? ? ? ? ? ? ? ? ? b=q[i].r;
?? ? ? ? ? ? ?}
?? ? ? ? ? ? ?else if(q[i].l<=b)
?? ? ? ? ? ? ?{
?? ? ? ? ? ? ? ? ? a=q[i].l;
?? ? ? ? ? ? ? ? ? if(q[i].r<b)
?? ? ? ? ? ? ? ? ? b=q[i].r;
?? ? ? ? ? ? ?}
?? ? ? ? }
?? ? ? ? printf("Case %d: %d\n",cas++,ans);
?? ? ? ??
?? ?}
?? ?return 0;
}
?? ? ? ??
?? ? ? ??
?? ? ? ? ? ? ?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
