2016年9月2日 星期五

UVA 1615 - Highway



題目概述:經典入門書p8-49
這提一直覺得怪怪的。
看書上寫的題意才知道意思。
給一些座標點,求至少需要多少出口使每個每個點離出口距離不大於D。


思路:
先對每個點都在x軸上找出能涵蓋到該點的區間l,r。然後再greedy。
待補。


//By SCJ
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define INF 10000000000000
struct P{
   double x1,x2;
}es[100001];
bool cmp(P a,P b)
{
   return a.x1<b.x1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
   double L,D;
   int n;
   while(cin>>L>>D>>n)
   {
       for(int i=0;i<n;++i)
       {
           double x,y;cin>>x>>y;
           double dx=sqrt(D*D-y*y);
           es[i]={x-dx,x+dx};
       }
       sort(es,es+n,cmp);
       double la=INF;
       int ans=0;
       for(int i=0;i<n;++i)
       {
           P e=es[i];
           if(e.x1>la) ans++,la=e.x2;
           else la=min(la,e.x2);
       }
       if(n==0) cout<<0<<endl;
       else cout<<ans+1<<endl;
   }
}

沒有留言:

張貼留言