message
message
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)的时候在凸包集合上二分查询与所求点斜率最大的点，维护斜率的最大值。
代码
#include<bits/stdc++.h>
#define ll long long
#define eps 1e-10
using namespace std;
const ll maxn=1e5+10;
struct node
{
double x,y;
ll id;
}p[maxn],s[maxn];
double ans[maxn];
double cross(node a,node b,node c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
ll dcmp(double x)
{
return fabs(x)<eps?0:x<0?-1:1;
}
bool operator <(node p1,node p2)
{
return dcmp(p1.x-p2.x)<0||(dcmp(p1.x-p2.x)==0&&dcmp(p1.y-p2.y)<0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
for(ll i=0;i<n;i++){
cin>>p[i].x>>p[i].y;
}
ll m;
cin>>m;
for(ll i=n;i<n+m;i++) cin>>p[i].x>>p[i].y,p[i].id=i;
for(ll i=0;i<n+m;i++) p[i].x=-p[i].x;
sort(p,p+n+m);
ll top=0;
for(ll i=0;i<n+m;i++){
if(p[i].id){
if(!top) continue;
ll l=1,r=top;
while(l<r){
ll mid=l+r>>1;
if(cross(s[mid],s[mid+1],p[i])<=0) r=mid;
else l=mid+1;
}
ans[p[i].id]=max(ans[p[i].id],(p[i].y-s[l].y)/(p[i].x-s[l].x));
}
else{
while(top>1&&dcmp(cross(s[top-1],s[top],p[i]))<=0) top--;
//如果是向右转，这个中间点就不是我们要找的点
s[++top]=p[i];//如果是向左转，就加进来
}
}
reverse(p,p+n+m);
top=0;
for(ll i=0;i<n+m;i++){
if(p[i].id){
if(!top) continue;
ll l=1,r=top,pos=1;
while(l<r){
ll mid=l+r>>1;
if(cross(s[mid],s[mid+1],p[i])<=0) r=mid;
else l=mid+1;
}
ans[p[i].id]=max(ans[p[i].id],(p[i].y-s[l].y)/(p[i].x-s[l].x));
}
else{
while(top>1&&dcmp(cross(s[top-1],s[top],p[i]))<=0) top--;
//如果是向右转，这个中间点就不是我们要找的点
s[++top]=p[i];//如果是向左转，就加进来
}
}
for(ll i=n;i<m+n;i++){
if(dcmp(ans[i])<=0) cout<<"No cross"<<endl;
else cout<<setiosflags(ios::fixed)<<setprecision(15)<<ans[i]<<endl;
}
return 0;
}
公司都抢着要
腾讯成长空间 449人发布