ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2008 Dragon Fantasy

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2008


・概要
勇者が各地に散らばったクリスタルを全部集めて、そのクリスタルの力で魔王を倒します。クリスタルを全部集められるかどうかを調べる問題です。
問題文が日本語なので省略。


・解法
枝刈りをしながらの全探索(dfs)で解くことができます。

(解法考える時に他の人のコードを少しチラ見してしまいました。 あとはビット演算の書き方を相変わらず忘れてしまったのでアリ本に助けてもらいました。)

探索する時は、[未訪問の場所(ビットで表す)、現在地、経過時間]の3つを持たせます。

枝刈りの対象となる(クリスタルを取りにいけない)のは、
魔王・あるクリスタル間の距離 < 経過時間+現在地・あるクリスタル間の距離
です。


double hypot(double x, double y)
今まで知らなかったので載せておきます。
sqrt(x^2 + y^2)と同じことができたんですね、これは楽チン!
オーバーフローを起こさないように設計されてるんだとか…?
(※#includeは必須)
(hypotenuse…斜辺)


ソースコード

#include<iostream>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
static const double EPS = 1e-8;

int n,hx,hy,dx,dy;
int x[20],y[20];
bool flag;

void dfs(int unvisit, int cx, int cy, double t){
   if(flag)return;
  
   if(unvisit==0)flag = true;
   
   else{
      //枝刈り
      rep(i,n){
	 if(!((unvisit >> i) & 1))continue;
	 if(hypot(dx-x[i], dy-y[i]) < t + hypot(cx-x[i], cy-y[i]) + EPS)return;
      }

      rep(i,n){
	 if(!((unvisit >> i) & 1))continue;
	 dfs((unvisit & ~(1 << i)), x[i], y[i], t + hypot(cx-x[i], cy-y[i]));
      }
   }
}

string solve(){
   flag = false;
   dfs((1<<n)-1, hx, hy, 0);
   return (flag) ? "YES" : "NO";
}

int main(){
   while(cin >> n >> hx >> hy >> dx >> dy){
      if((n|hx|hy|dx|dy)==0)break;
   
      rep(i,n){
	 cin >> x[i] >> y[i];
      }
      
      cout << solve() << endl;
   }
   return 0;
}