POJ 1328 Radar Installation 贪心难度:1

http://poj.org/problem?id=1328

思路:

1.肯定y大于d的情况下答案为-1,其他时候必定有非负整数解

2.x,y同时考虑是较为麻烦的,想办法消掉y,用d^2-y^2获得圆心允许范围,问题转化为在许多圆心允许范围内取尽可能少的点,也即在许多线段上取尽可能少的点,使得所有线段上都有点被取到

3.从左往右考虑,完全在左边的线段肯定要取点,如果这个点在当前线段上已经取了,明显就可以忽略当前线段,明显在线段上的最优点是右端点

  1 #include <iostream>
  2 #include <cmath>
  3 using namespace std;
  4 
  5 
  6 typedef pair<double,double> p;
  7 p pos[1005];
  8 p temp[1005];
  9 int n,d;
 10 
 11 int MERGE(int s,int e){
 12     int mid=(e+s)/2;
 13     int i=s,j=mid,k=s;
 14     while(i<mid&&j<e){
 15         if(pos[i].first>pos[j].first||(pos[i].first==pos[j].first&&pos[i].second>pos[j].second)){
 16             temp[k].first=pos[j].first;
 17             temp[k].second=pos[j].second;
 18             k++;
 19             j++;
 20         }
 21         else {
 22                 temp[k].first=pos[i].first;
 23                 temp[k].second=pos[i].second;
 24                 k++;
 25                 i++;
 26         }
 27     }
 28     int kk=k;
 29     for(;i<mid;i++){
 30         pos[kk].first=pos[i].first;
 31         pos[kk].second=pos[i].second;
 32         kk++;
 33     }
 34     for(int ii=s;ii<k;ii++){
 35         pos[ii].first=temp[ii].first;
 36         pos[ii].second=temp[ii].second;
 37     }
 38     return 0;
 39 }
 40 int MERGE_SORT1(int s,int e){
 41     if(e-s<2){
 42         return 0;
 43     }
 44     int mid=(s+e)/2;
 45     MERGE_SORT1(s,mid);
 46     MERGE_SORT1(mid,e);
 47     MERGE(s,e);
 48     return 0;
 49 }
 50 
 51 int solve(){
 52     double x,y;
 53     double sq;
 54     bool flag=false;
 55     for(int i=0;i<n;i++){
 56         cin>>x>>y;
 57         if(y>d){
 58             flag=true;
 59             continue;
 60         }
 61         if(y<0){
 62             i--;
 63             n--;
 64             continue;
 65         }
 66         sq=sqrt((double)(d*d-y*y));
 67         pos[i].first=x-sq;
 68         pos[i].second=x+sq;
 69     }
 70     if(flag)return 0;
 71     MERGE_SORT1(0,n);
 72     int ans=1;
 73     double mx;
 74     mx=pos[0].second;
 75     for(int i=1;i<n;i++){
 76         if(mx<pos[i].first){
 77             ans++;
 78             mx=pos[i].second;
 79         }
 80         else if(mx>pos[i].second){
 81             mx=pos[i].second;
 82         }
 83     }
 84     return ans;
 85 }
 86 
 87 int main(){
 88     int ci=1;
 89     while(ci++){
 90         cin>>n>>d;
 91         if(n<=0)break;
 92         int ans=solve();
 93         if(ans){
 94             cout<<"Case "<<ci-1<<":"<<" "<<ans<<endl;
 95         }
 96         else{
 97             cout<<"Case "<<ci-1<<":"<<" "<<-1<<endl;
 98          }
 99     }
100     return 0;
101 }

View Code

POJ 1328 Radar Installation 贪心 难度:1

POJ 1328 Radar Installation 贪心难度:1