UVa 10382 : Watering Grass

問題リンク：http://uva.onlinejudge.org/external/103/10382.html

問題概要：
略

解法：
円と長方形が交差する場所のx座標を計算で求める
円の中心点の座標を(x,y)、円の半径をrとすると
円と長方形が交差する場所のx座標(以下 nx)は以下の通り
nx = +sqrt(r*r-(l/2)*(l/2)),-sqrt(r*r-(l/2)*(l/2))
この情報を円毎に作っておく

全ての場所をスプリンクラーがカバーしないといけないため、
左(または右)から貪欲に決める亊ができる
最初まだカバーされていない点をx = 0とする
左から右へ向かうとすると、
長方形と交差する場所の間にxを含むような円の中でもっとも右にすすめる円を選ぶ
そしてxにその右の場所を代入する
これをxがwをこえるまで繰り返す

その過程でどうしても全てをカバーできない亊が分かったら-1と出力し終了する

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define EPS (1e-10)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

struct P
{
  double left,right;
  P(double left=inf,double right=inf):left(left),right(right){}
};

struct Point
{
  double x,y;
  Point(double x=inf,double y=inf):x(x),y(y){}
};

int n;
double h,w;
vector<Point> vec;

void compute()
{
  P cs[n];
  rep(i,n)
    {
      double y = h * 0.5;
      assert(vec[i].y*vec[i].y - y * y >= 0);
      double x = sqrt(vec[i].y*vec[i].y - y*y);
      cs[i].right = vec[i].x+x;
      cs[i].left  = vec[i].x-x;
    }

  double x = 0;
  double pre_x = -1;
  int cnt = 0;
  while(!equals(x,w) && x < w)
    {
      int pos = -1;
      rep(i,n)
	{
	  double L = cs[i].left;
	  double R = cs[i].right;
	  if(L <= x && x <= R)
	    {
	      if(pos == -1)pos = i;
	      else
		{
		  if(cs[pos].right < R)
		    {
		      pos = i;
		    }
		}
	    }
	}

      if(pos == -1)
	{
	  cout << -1 << endl;
	  return;
	}
      pre_x = x;
      x = cs[pos].right;
      if(equals(pre_x,x))
	{
	  cout << -1 << endl;
	  return;
	}

      x = cs[pos].right;
      cnt++;
    }
  cout << cnt << endl;
}

int main()
{
  while(scanf("%d %lf %lf",&n,&w,&h) != EOF)
    {
      vec.resize(n);
      rep(i,n)scanf("%lf %lf",&vec[i].x,&vec[i].y);

      compute();

    }
  return 0;
}