vp时c题用自已的方法过了,赛后补下正解
C.Place for a Selfie
题意
给定一些抛物线和过原点的直线,对于每个抛物线,是否存在一条直线与它相交。
思路
联系\(y=kx\)和\(y=ax^2+bx+c\),可得\(ax^2+(b-k)x+c=0\)。如果无解要满足,\(b^2-4ac<0\)即\(k^2-2bk+b^2-4ac<0\)。因为题目给的抛物线是开口向上的,所以在对称轴位置也就是\(k\)取\(b\)时不等式左边最小。
所以对\(k\)进行排序,在二分查找后判断不等式是否成立即可。
代码
bool func(int a, int b, int c) {
return 1ll * b * b < 4ll * a * c;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> k(n);
for(int i = 0; i < n; i++) {
cin >> k[i];
}
sort(k.begin(), k.end());
while(m--) {
int a, b, c;
cin >> a >> b >> c;
auto it = lower_bound(k.begin(), k.end(), b);
if(it != k.end() && func(a, b - *it, c)) {
cout << "YES\n" << *it << "\n";
}
else if(it != k.begin() && func(a, b - *prev(it), c)) {
cout << "YES\n" << *prev(it) << "\n";
}
else {
cout << "NO\n";
}
}
}