传送门：https://ac.nowcoder.com/acm/problem/16631
题意
对于直线y=ax+b，给出n个的a[i]和b[i]。m次询问，每次询问给出直线y=cx+d的c[i]和d[i]，如果和给出的n个直线交点的最大横坐标>0，则输出横坐标，否则输出 No cross。
题解
y=ax+b ①
y=cx+d ②
联立①②得：x = - (b-d) / (a-c) = (b-d) / (-a-(-c))。
可以看出 x 就是将所有的横坐标取相反数之后点 (-a,b) 和点(-c,d) 所在的直线的斜率，那么问题就转换成了求最大斜率。
这个问题可以用凸包求解。用到了Andrew算法（没懂为啥Graham算法写出来的不对）Andrew算法可以看这里：https://www.cnblogs.com/mudrobot/p/13330937.html
因为记录凸包点的数组是具有单调性的，所以可以当每次遇到(c,d)的时候在凸包集合上二分查询与所求点斜率最大的点，维护斜率的最大值。
代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define eps 1e-10 4 using namespace std; 5 6 const ll maxn=1e5+10; 7 8 struct node 9 { 10 double x,y; 11 ll id; 12 }p[maxn],s[maxn]; 13 14 double ans[maxn]; 15 16 double cross(node a,node b,node c) 17 { 18 return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); 19 } 20 21 ll dcmp(double x) 22 { 23 return fabs(x)<eps?0:x<0?-1:1; 24 } 25 26 bool operator <(node p1,node p2) 27 { 28 return dcmp(p1.x-p2.x)<0||(dcmp(p1.x-p2.x)==0&&dcmp(p1.y-p2.y)<0); 29 } 30 31 int main() 32 { 33 ios::sync_with_stdio(false); 34 cin.tie(0); 35 cout.tie(0); 36 ll n; 37 cin>>n; 38 for(ll i=0;i<n;i++){ 39 cin>>p[i].x>>p[i].y; 40 } 41 ll m; 42 cin>>m; 43 for(ll i=n;i<n+m;i++) cin>>p[i].x>>p[i].y,p[i].id=i; 44 for(ll i=0;i<n+m;i++) p[i].x=-p[i].x; 45 sort(p,p+n+m); 46 ll top=0; 47 for(ll i=0;i<n+m;i++){ 48 if(p[i].id){ 49 if(!top) continue; 50 ll l=1,r=top; 51 while(l<r){ 52 ll mid=l+r>>1; 53 if(cross(s[mid],s[mid+1],p[i])<=0) r=mid; 54 else l=mid+1; 55 } 56 ans[p[i].id]=max(ans[p[i].id],(p[i].y-s[l].y)/(p[i].x-s[l].x)); 57 } 58 else{ 59 while(top>1&&dcmp(cross(s[top-1],s[top],p[i]))<=0) top--; 60 //如果是向右转，这个中间点就不是我们要找的点 61 s[++top]=p[i];//如果是向左转，就加进来 62 } 63 } 64 reverse(p,p+n+m); 65 top=0; 66 for(ll i=0;i<n+m;i++){ 67 if(p[i].id){ 68 if(!top) continue; 69 ll l=1,r=top,pos=1; 70 while(l<r){ 71 ll mid=l+r>>1; 72 if(cross(s[mid],s[mid+1],p[i])<=0) r=mid; 73 else l=mid+1; 74 } 75 ans[p[i].id]=max(ans[p[i].id],(p[i].y-s[l].y)/(p[i].x-s[l].x)); 76 } 77 else{ 78 while(top>1&&dcmp(cross(s[top-1],s[top],p[i]))<=0) top--; 79 //如果是向右转，这个中间点就不是我们要找的点 80 s[++top]=p[i];//如果是向左转，就加进来 81 } 82 } 83 for(ll i=n;i<m+n;i++){ 84 if(dcmp(ans[i])<=0) cout<<"No cross"<<endl; 85 else cout<<setiosflags(ios::fixed)<<setprecision(15)<<ans[i]<<endl; 86 } 87 return 0; 88 }