算法题目——岛屿问题(POJ-1328)

朴灿烈づ我的快乐病毒、 2022-09-12 13:46 180阅读 0赞

[POJ-1328][]  
题目大意：在x轴上建立尽量少的雷达覆盖所有的岛屿。

Input：岛屿的数量n，雷达覆盖半径d.接下来的n行一行表示一个岛屿(x,y).

Output:每个案例的雷达最少数目.  
经典的区间选点！

要搞清楚为什么排序，然后要明白如何选点。

思想（排序原因）：小区间被满足，大区间一定被满足。

(所以排序后所有岛屿都是 递增的！)(即小区间都在前面。)

选点：只有前一个点的右端点小于下一个点的左端点，这时才选一个点（即增加一个雷达）因为不可能存在一个雷达可以覆盖到这两个岛屿，而且此时前面用一个雷达覆盖即为最优解！（因为大区间包含了小区间）

#include<iostream>
    #include<algorithm>
    #include<math.h>
    #include <stdlib.h>
    #include<vector> 
    using namespace std;
     struct point{
        
    	double left,right;
    }p[2021],temp;
    
    bool operator <(point a,point b)
    {
        
    	return a.left<b.left;
    }
    int main()
    {
        
    	int n;//岛屿的数量
    	double r;//雷达半径
    	vector<int> vec;
    	while(cin>>n>>r&&(n||r))
    	{
        
    		int a,b;
    		int flag=1;
    		
    		for(int i=0;i<n;i++)
    		{
        
    			cin>>a>>b;
    			
    			if(b>r)
    			{
        
    				flag=0;
    			}
    			else
    			{
        
    				p[i].left = a * 1.0 - sqrt(r * r - b * b);
    				p[i].right = a * 1.0 + sqrt(r * r - b * b);
    			}
    		
    		}
    
    		if(flag==0)
    		{
        
    			vec.push_back(-1);
    			 	
    		 } 
    		 else
    		 {
        
    		 	int count=1;//雷达的个数
    			sort(p,p+n);
    			temp= p[0];
    						
    						
    			for(int i=1;i<n;i++)
    			{
        
    				if(p[i].left>temp.right)
    				{
        
    					count++;
    					temp=p[i];
    				}
    				else if(p[i].right<temp.right)
    					{
        
    						temp=p[i];
    					}				
    			 }
    			 vec.push_back(count);
    		 }
    	
    			 
    		
      }
      	int kase=0;
    	
      	int num=vec.size();
     	for(int i=0;i<num;i++)
     	{
        
     		cout << "Case " << ++kase << ": ";
     		cout<<vec[i]<<endl;
    	 }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]

[POJ-1328]: http://poj.org/problem?id=1328
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/17758665519f4b52b0149a2f5569e4a2.png