結果

問題 No.168 ものさし
ユーザー __NCAstar__NCAstar
提出日時 2015-03-20 00:02:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 661 ms / 2,000 ms
コード長 1,357 bytes
コンパイル時間 2,789 ms
コンパイル使用メモリ 166,008 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-06 14:47:01
合計ジャッジ時間 4,461 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 167 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 16 ms
5,376 KB
testcase_11 AC 58 ms
5,376 KB
testcase_12 AC 265 ms
5,376 KB
testcase_13 AC 520 ms
5,376 KB
testcase_14 AC 24 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 10 ms
5,376 KB
testcase_18 AC 7 ms
5,376 KB
testcase_19 AC 170 ms
5,376 KB
testcase_20 AC 129 ms
5,376 KB
testcase_21 AC 661 ms
5,376 KB
testcase_22 AC 102 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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