結果
| 問題 | No.168 ものさし |
| ユーザー |
 dnish
|
| 提出日時 | 2018-03-06 10:55:23 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,472 bytes |
| コンパイル時間 | 838 ms |
| コンパイル使用メモリ | 87,800 KB |
| 実行使用メモリ | 30,476 KB |
| 最終ジャッジ日時 | 2024-09-15 12:21:18 |
| 合計ジャッジ時間 | 7,402 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge6 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
ソースコード
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll inf = 1e10;
int N;
ll x[1010],y[1010];
ll d[1010][1010];
bool visited[1010];
//答えが整数の時
bool C(ll mid){//ここに条件を書く
queue<int> q;//ノード
REP(i,0,N) visited[i]=false; //初期位置を設定
q.push(0);
while(!q.empty()){
int curNode = q.front();
q.pop();
visited[curNode] = true;
REP(i,0,N){
if(!visited[i]&&d[curNode][i]<=mid*mid) q.push(i);
}
}
//lbが更新される不等式を書く
return !visited[N-1];
}
ll nibutan(){
ll lb=0,ub=inf;
while(ub-lb>10){
ll mid=(lb+ub)/2;
if(mid%10!=0) mid=(mid/10+1)*10;
if(C(mid)) lb=mid;
else ub=mid;
//cout<<lb<<" "<<ub<<endl;
}
return ub;
}
int main() {
cin>>N;
REP(i,0,N){
cin>>x[i]>>y[i];
}
REP(i,0,N){
REP(j,0,N){
d[i][j]=(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
}
}
ll ans=nibutan();
p(ans);
return 0;
}