Codeforces Round 862 (Div. 2) - C. Place for a Selfie (1400)

C. Place for a Selfie

이차함수의 판별식은 $ax^2+bx+c$ 에서 $D=b^2-4ac$ 이고 이것이 해가 없으려면 모든 $k$ 에 대해

$ax^2+(b-k)x+c=0$ 의 방정식에서 $D=(b-k)^2-4ac < 0$ 여야 한다.

이 부등식을 풀면

$$ \begin{aligned} (b-k)^2 &< 4ac \\ -\sqrt{ 4ac } < \vert b-k \vert &< \sqrt{ 4ac } \\ -\sqrt{ 4ac } < k-b &< \sqrt{ 4ac } \\ b-\sqrt{ 4ac } < k &< b+\sqrt{ 4ac } \end{aligned} $$

가 되어야 한다.

이걸 이분탐색으로 잘 구해주면 된다.

void solve() {
   int n, m;
   cin >> n >> m;
   vi k(n);
   fv(k);
   sort(all(k));
   for (int i = 0; i < m; i++) {
      double a, b, c;
      cin >> a >> b >> c;
 
      double t = b - sqrt(4 * a * c);
 
      int j = ubi(k, b) - 1;
      // 1
      if (j >= 0) {
         if (k[j] > t) {
            cout << "YES\n";
            cout << k[j] << endl;
            continue;
         }
      }
      j++;
      if (j < n) {
         if (k[j] < b + sqrt(4 * a * c)) {
            cout << "YES\n";
            cout << k[j] << endl;
            continue;
         }
      }
      cout << "NO\n";
   }
}