Hatena::Grouptopcoder

thorikawa@top coder

topcoder id: the_poly
 | 

2013-02-22

TopCoder - SRM Div1 Hard

16:27 | はてなブックマーク - TopCoder - SRM Div1 Hard - thorikawa@top coder

1000解いた。

1000 CandyOnDisk

2つのDiskが重なっている場合、それぞれの間を行き来可能な領域が存在する。この領域はバームクーヘンか円のIntersectionとして表現できる。全Diskを考えるとき、行き来可能な領域が重なっていれば、それらは合併することができるので、union findでつないで、(sx,sy)と(tx,ty)が行き来可能かどうかを調べることができる。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

int parent[3000] = {-1};

int root (int i) {
  if(parent[i] == i) return i;
  else return root(parent[i]);
}
void unite (int i, int j) {
  int p1 = root(i);
  int p2 = root(j);
  if(p1==p2) return;
  else {
    parent[p2] = p1;
    return;
  }
}

inline int id(int i, int j) {
  return i*52+j;
}

class CandyOnDisk {
public:
string ableToAchieve(vector <int> rawx, vector <int> rawy, vector <int> rawr, int sx, int sy, int tx, int ty) {
  int i,j,k;

  // obvious check
  if (sx == tx && sy == ty) return "YES";
  REP(i,rawx.size()){
    double dx1 = (sx-rawx[i]);
    double dy1 = (sy-rawy[i]);
    double dx2 = (tx-rawx[i]);
    double dy2 = (ty-rawy[i]);
    double d1 = sqrt(dx1*dx1 + dy1*dy1);
    double d2 = sqrt(dx2*dx2 + dy2*dy2);
    if (d1 == d2 && d1 <= rawr[i]) {
      return "YES";
    }
  }

  // pre process
  // remove concentric circles
  vector<int> x;
  vector<int> y;
  vector<int> r;
  REP(i,rawx.size()){
    // check rawx[i] and rawy[i]
    bool exist = false;
    REP(j,x.size()){
      if (rawx[i] == x[j] && rawy[i] == y[j]) {
        r[j] = max(r[j], rawr[i]);
        exist = true;
        break;
      }
    }
    if (!exist) {
      x.push_back(rawx[i]);
      y.push_back(rawy[i]);
      r.push_back(rawr[i]);
    }
  }
  
  // initialize
  int n = x.size();
  double minr[52][52];
  double maxr[52][52];
  REP(i,n) REP(j,n) {
    minr[i][j] = 100;
    maxr[i][j] = 0;
  }
  REP(i,3000){
    parent[i] = i;
  }
  
  int sid = -1;
  int tid = -1;

  REP(i,n) {
    double sdx = sx - x[i];
    double sdy = sy - y[i];
    double tdx = tx - x[i];
    double tdy = ty - y[i];
    double sr = sqrt(sdx*sdx + sdy*sdy);
    double tr = sqrt(tdx*tdx + tdy*tdy);

    REP(j,n) {
      if (i==j) continue;
      double dx = x[i]-x[j];
      double dy = y[i]-y[j];
      double d = sqrt(dx*dx + dy*dy);
      if (r[i] >= d+r[j]) {
        // r[i] covers r[j]
        minr[i][j] = max(0.0, d-r[j]);
        maxr[i][j] = d+r[j];
      } else if (r[j] >= d+r[i]) {
        // r[j] covers r[i]
        minr[i][j] = 0.0;
        maxr[i][j] = r[i];
      } else if (d <= r[i]+r[j]) {
        // intersect
        minr[i][j] = max(0.0, d-r[j]);
        maxr[i][j] = r[i];
      }
      
      if (sr <= maxr[i][j] && sr >= minr[i][j]) {
        sid = id(i,j);
      }
      if (tr <= maxr[i][j] && tr >= minr[i][j]) {
        tid = id(i,j);
      }
    }
  }
  
  // union find
  REP(i,n) {
    REP(j,i) {
      if (maxr[i][j] >= minr[i][j]) {
        unite(id(i,j), id(j,i));
      }
    }
  }
  REP(i,n) {
    REP(j,n) {
      if (i==j) continue;
      REP(k,n) {
        // compare (i,k) and (j,k) 
        if (i==k || j==k) continue;
        if (maxr[k][i] < minr[k][i]) {
          continue;
        }
        if (maxr[k][j] < minr[k][j]) {
          continue;
        }
        if (!(maxr[k][i] < minr[k][j] || maxr[k][j] < minr[k][i])) {
          // intersect
          unite(id(k,i), id(k,j));
        }
      }
    }
  }
  if (sid == -1 || tid == -1) {
    return "NO";
  }
  if (root(sid) == root(tid)) {
    return "YES";
  }
  
  return "NO";
}


 |