B - Light It Up Editorial by physics0523
ある人が少なくとも \(1\) つの明かりに照らされるとは、どういうことでしょうか?
実は、これは「ある人から距離 \(R\) 以内に明かりを持った人が少なくとも \(1\) 人いる」と言い換えることができます。
さらにこれを言い換えると、「ある人から最も近い『明かりを持った人』が距離 \(D\) の位置にいるとすると、 \(D \le R\) であるとき、ある人は少なくとも \(1\) つの明かりに照らされる」と言い換えられます。
結局、この問題の答えは、全ての人について、その人から最も近い『明かりを持った人』までの距離の最大値となります。そして、これは二重ループによって時間計算量 \(O(NK)\) で求めることが出来ます。
注意点1: 距離の比較を行う時には、可能なら整数性を崩さずに比較を行いましょう。
具体的には、 \(2\) 点 \((a,b),(c,d)\) 間の距離は \(\sqrt{(a-c)^2+(b-d)^2}\) ですが、この根号内が整数なら、大小の評価などを根号内の整数で行った上で、出力を行ったりと実数値が必要になったタイミングで \(\sqrt{}\) をとることをおすすめします。
注意点2: 出力形式に注意してください。
たとえば 2.55e22
のような指数表記は、競技プログラミングにおいて不正解として扱われることがあります。特別な指示がない限り指数表記を使わずに出力することを推奨します。
また、出力する桁数が少ないと、せっかく十分精度がある答えを求めることが出来ても出力する際に許容される誤差を超えてしまう可能性があるので、許容誤差に対して十分多い桁数を出力することを推奨します。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin >> n >> k;
vector<int> a(k);
for(auto &nx : a){
cin >> nx;
nx--;
}
vector<long long> x(n),y(n);
for(int i=0;i<n;i++){cin >> x[i] >> y[i];}
long long res=0;
for(int i=0;i<n;i++){
long long cres=8e18;
for(auto &nx : a){
cres=min(cres,(x[i]-x[nx])*(x[i]-x[nx]) + (y[i]-y[nx])*(y[i]-y[nx]));
}
res=max(res,cres);
}
printf("%.12lf\n",sqrt((double)res));
return 0;
}
posted:
last update: