Official

B - Light It Up Editorial by en_translator


What does it mean by “every person is lit by at least one light?”
Actually, this holds if and only if “for every person, there is at least one person at the distance at most \(R\).”
This can be further rephrased: “a person is lit by a light if \(D \le R\), where \(D\) is the distance between the person and the nearest person with a light.”

After all, the answer to this problem is the maximum distance for every person to the nearest “person with a light,” which can be found with a double loop in a total of \(O(NK)\) time.

Note 1: resort to integers when comparing distances if possible.
Specifically, the distance between two points \((a,b)\) and \((c,d)\) is \(\sqrt{(a-c)^2+(b-d)^2}\); it is recommended that, if the radicand is an integer, then we can compare the distances by the radicand, calculating the \(\sqrt{}\) when the real value is needed as in output.

Note 2: be careful how to output the result.
For example, the exponential notation like 2.55e22 may be judged wrong in competitive programming. Unless noted otherwise, we recommend you to output without using the exponential notation.
Also, if not enough digits are output, the output may deviate over the permitted error even if the computation is correct, so it is recommended to output enough number of digits.

Sample code (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: