No.168 ものさし - yukicoder
- 二分探索を使う問題
- 10^9 まである座標を hypot につっこんで計算して精度落ちしてしまった...。
- あと何気に最後の cout で long long にキャストせずに WA してしまった...。出力時にキャストしわすれないようにしよう。
class Ruler {
public:
void solve(void) {
int N;
cin>>N;
vector<ll> xs(N);
vector<ll> ys(N);
REP(i,N)
{
cin>>xs[i]>>ys[i];
}
vector<vector<ll>> dist(N,vector<ll>(N,0));
REP(i,N)
REP(j,i+1)
{
ll dx = xs[i]-xs[j];
ll dy = ys[i]-ys[j];
dist[i][j] = dist[j][i] = dx*dx+dy*dy;
}
ll low = 0;
ll high = 2*1E+9+1;
vector<bool> vis(N,false);
while (low+1 < high)
{
ll mid = (low+high)/2;
fill(RANGE(vis),false);
function<void(int)> dfs = [&](int v) {
vis[v] = true;
REP(u,N)
{
if (vis[u])
continue;
if (dist[v][u] > mid*mid)
continue;
dfs(u);
}
};
dfs(0);
if (vis[N-1])
high = mid;
else
low = mid;
}
cout<<(ll)ceil(high/10.0)*10<<endl;
}
};