結果

問題 No.168 ものさし
ユーザー __NCAstar
提出日時 2015-03-20 00:02:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 641 ms / 2,000 ms
コード長 1,357 bytes
コンパイル時間 1,464 ms
コンパイル使用メモリ 166,304 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 06:56:31
合計ジャッジ時間 4,293 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

#define double long double

struct Point {
  double x,y;
};

typedef long long ll;

int n;
vector<Point> vec;
bool visited[1010];


bool LTE(double a,double b) { return equals(a,b) || a < b; }

#define pow2(x) ((x)*(x))
bool check(double length){
  //ll len = ceil(length); 
  double len = length * length;
  //ll len = length * length
  //while( len % 10 ) ++len;
  memset(visited,false,sizeof(visited));
  deque<int> deq;
  visited[0] = true;
  deq.push_back(0);

  while( !deq.empty() ){
    int cur = deq.front(); deq.pop_front();
    if( cur == n-1 ) return true;
    rep(next,n) if( !visited[next] ) {
      double dist = pow2(vec[cur].x-vec[next].x)+pow2(vec[cur].y-vec[next].y);
      //if( LTE(dist,len) ) {
      if( dist < len ) {
	visited[next] = true;
	deq.push_back(next);
      }
    }
  }
  return false;
}

void compute(){
  double L = 0, R = 1e10;
  rep(_,200){
    double M = ( L + R ) / 2.0;

    if( check(M) ) R = M;
    else           L = M;
  }
  ll answer = (ll)ceil(L);
  while( answer % 10 ) ++answer;

  cout << answer << endl;
}

int main(){
  cin >> n;
  vec.clear();
  vec.resize(n);
  rep(i,n) cin >> vec[i].x >> vec[i].y;
  compute();
  return 0;
}
0