T3 拍照 50分WA
题目描述
鱼大大非常非常喜欢玩车，每次的汽车拉力赛都会带上摄像机为自己喜欢的赛车留下最酷炫的照片。
赛车在转弯时速度稍慢，此时鱼大大才容易多角度拍出好看的照片。当然！拍大片的同时也要保证自己的人生安全，不影响到比赛的同时也千万不能被赛车撞了。
赛车的入弯出弯的路线可以看做一条开口向上的抛物线(y= ax^2 + bx + c)，鱼大大的拍照路线可以看做一条经过看台直线(y = kx，看台作为0点)。
鱼大大拍照事先准备好了多条拍摄路线，问对于每一辆鱼大大喜爱的赛车，能否找到一条安全的路线让鱼大大拍照？
【题面简述】
给定顺序的每个抛物线。只要有一条线不与给定的抛物线相交并且不接触它，在对应的单独行上输出单词“YES”。若是所有直线都和该抛物线相交，则输出“NO”。
输入格式
第一行两个整数 n, m；分别表示鱼大大的拍照路线(直线)和赛车过弯路线(抛物线)
接下来n行每行一个整数k，表示直线方程式(y = kx)的斜率
接下来m行每行三个整数a,b,c；表示抛物线方程式(y= ax^2 + bx + c)的各个系数
输出格式
m行，每一行用“YES”或“NO”表示对应的赛车过弯时，鱼大大是否有拍照的安全路线
样例
Input 1
2 2 1 4 1 2 1 2 5 1
Output 1
YES YES
Input 2
2 3 0 2 2 2 1 1 -2 1 1 -2 -1
Output 2
YES NO NO
样例解释
鱼大大有两辆喜爱的赛车，
他们的过弯路径抛物线分别是
y = 1x^2 + 2x + 1 和 y = 2x^2 + 5x + 1。
鱼大大的拍摄路径也有两条，分别为为 y = 1x 和 y = 4x。(https://staticw.turingstar.com.cn/202305091045/e6a2af0e0edb83de1b122531c9c0d8a6/ffc42fae-a817-4104-8f26-494846f231c5)
由图可看出：y = 1x^2 + 2x + 1 不和 y = x 有任何交点，所以有安全路线，输出YES；
y = 2x^2 + 5x + 1 不和 y = 4x 有任何交点，所以有安全路线，输出YES。
数据范围
1≤n,m≤100000
1≤a≤100000
0≤∣b∣,∣c∣,∣k∣≤100000
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int f1[N],f2[N][5],m,n;
bool check(int x){
long long a=f2[x][1],b=f2[x][2],c=f2[x][3];
int k=lower_bound(f1+1,f1+m+1,b)-f1;
if((b-f1[k])*(b-f1[k])-4*a*c<0)return true;
if((b-f1[k-1])*(b-f1[k-1])-4*a*c<0)return true;
return false;
}
int main(){
cin >> m >> n;
for(int i=1;i<=m;++i)scanf("%lld",&f1[i]);
for(int i=1;i<=n;++i)scanf("%lld %lld %lld",&f2[i][1],&f2[i][2],&f2[i][3]);
for(int i=1;i<=n;++i){
if(check(i))printf("YES\n");
else printf("NO\n");
}
}