UVA 1615 - Highway

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;

   }

}