2018 牛客多校第二場 C message

題意：

給出n條直線，詢問m次，每次詢問給出一條直線，問這條直線與那n條直線的在y軸右側交點的橫坐标的最大值。

題解：

設交點為

，則

要使x最大，我将一條直線的兩個系數a、b看做點（a，b），那麼答案就是n個點中到詢問點的斜率的最小值。

為了友善和便于了解，我們将x坐标取反，轉為求斜率的最大值。

求上圖黑點到紅點的斜率最大值，可以變為隻求下圖連線中的點的斜率

那些連線上方的點一定不是最優解

是以我們要做的就是維護一個凸包

詢問某個點時，答案就是凸包中與詢問點相切的點

這個找相切的點的過程可以用二分查找，原因如下

對于切點左側的點，相鄰兩點組成的向量與向量a的叉積大于0,

對于切點右側的點，相鄰兩點組成的向量與向量a的叉積小于0,

滿足大于0的最右面的點就是答案需要的點

當然，答案也可能是這種情況

是以我們需要反過來再求一次

代碼：

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lower_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;

struct Point
{
    LL x,y;LL id;
    Point (LL x=0,LL y=0):x(x),y(y){}
    bool operator < (const Point z)
    {
        return x==z.x?y<z.y:x<z.x;
    }
    double K()
    {
        return (double)y/x;
    }
}a[N],b[N];
double ans[N];

typedef Point Vector;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
LL Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉積

void spy(int n)
{
    int m = 0;
    for(int i = 0; i < n; i++)
        if (a[i].id)
        {
            if (!m) continue;
            int l=1,r=m-1,t=0,v=0;
            while(l<=r)
            {
                int t=l+r>>1;
                if (Cross(b[t]-b[t-1],a[i]-b[t])>=0)
                    v=t,l=t+1;else r=t-1;
            }
            ans[a[i].id]=max(ans[a[i].id],(a[i]-b[v]).K());
        }
        else
        {
            while(m > 1 && Cross(b[m-1] - b[m-2], a[i]-b[m-2]) <= 0) m--;
            b[m++] = a[i];
        }
}



int main()
{
    int n,m;
    while(~sc(n))
    {
        for (int i=0;i<n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].id=0;
        sc(m);
        for (int i=n;i<n+m;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].id=i-n+1;
        for (int i=1;i<=m;i++) ans[i]=-1;
        for (int i=0;i<n+m;i++) a[i].x=-a[i].x;
        sort(a,a+n+m);
        spy(n+m);
        reverse(a,a+n+m);
        spy(n+m);
        for (int i=1;i<=m;i++)
            if (ans[i]<0) puts("No cross");else
                printf("%.8f\n",ans[i]);
    }
}