結果
問題 | No.168 ものさし |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }