C. Place for a Selfie

이차함수의 판별식은 ax2+bx+cax^2+bx+c 에서 D=b2−4acD=b^2-4ac 이고 이것이 해가 없으려면 모든 kk 에 대해

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

이 부등식을 풀면

(b−k)2<4ac−4ac<∣b−k∣<4ac−4ac<k−b<4acb−4ac<k<b+4ac \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";
   }
}

Comments

You may also enjoy