CF862 div2 C. Place for a Selfie

﹏ヽ暗。殇╰゛Y 2024-03-24 13:45 68阅读 0赞

[Problems - Codeforces][]

题意：

有一些直线和抛物线，对于一个抛物线，输出一个直线使得抛物线和直线没有交点

![b95935f9edbb46379440ff7a75ec4ad9.png][]

思路：

我们联立两个方程

y = kx

y = ax ^ 2 + bx + c

⇓

ax^2 + x \* (b -k) + c = 0

如果无解要满足

b^ 2 - 4ac < 0 即 k ^ 2 - 2bk + b ^ 2 - 4ac < 0，所以我们只要找到一个 k 满足上式就可以了，因为这是一个开口向上的二次函数，当 k 取对称轴的时候最小，也就是取 b 的时候，所以我们搞个set 然后二分就行了

注意判断lower\_bound位置的合法性，wa就wa在这了

如果二分出来的位置是pos，当且仅当pos>=1&&pos<=n时是合法的

Code:

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    struct ty{
        int a,b,c;
    }p[mxn];
    int n,m;
    i64 k[mxn];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>k[i];
        sort(k+1,k+1+n);
        for(int i=1;i<=m;i++) cin>>p[i].a>>p[i].b>>p[i].c;
        for(int i=1;i<=m;i++){
            int pos=lower_bound(k+1,k+1+n,p[i].b)-k;
            int delta1=0,delta2=0;
            delta1=(p[i].b-k[pos])*(p[i].b-k[pos])-4*p[i].a*p[i].c;
            delta2=(p[i].b-k[pos-1])*(p[i].b-k[pos-1])-4*p[i].a*p[i].c;
            if(delta1<0&&pos>=1&&pos<=n){
                cout<<"YES"<<'\n';
                cout<<k[pos]<<'\n';
                continue;
            }
            if(delta2<0&&pos-1>=1&&pos-1<=n){
                cout<<"YES"<<'\n';
                cout<<k[pos-1]<<'\n';
                continue;
            }
            cout<<"NO"<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problems - Codeforces]: https://codeforces.com/contest/1805/problems
[b95935f9edbb46379440ff7a75ec4ad9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ef2df17f6f3648358aeccdd864b4c483.png