C++14(g++5.4) 解法, 执行用时: 115ms, 内存消耗: 4832K, 提交时间: 2018-07-23 01:31:16

#include<bits/stdc++.h>
#define maxn 123456

using namespace std;
typedef long long ll;
struct point{ll x,y,id;}a[maxn],c[maxn];
bool cmp(point u,point v){return u.x<v.x;}
ll n,m,t,l,r,p,q;
double ans[maxn];
double calc(point u,point v){return (double)1.0*(u.y-v.y)/(v.x-u.x);}

void solve(){
    t=0;
    for (int i=0;i<n+m;i++){
        if (a[i].id){
            l=1; r=t;
            if (t==0||a[i].y>c[1].y) continue;
            while (r-l>2){
                p=(l*2+r)/3;
                q=(l+r*2)/3;
                if (calc(c[p],a[i])>calc(c[q],a[i])) r=q; else l=p;
            }
            for (int j=l;j<=r;j++) ans[a[i].id]=max(ans[a[i].id],calc(c[j],a[i]));
        }
        else{
            while (t>0&&a[i].y>c[t].y) t--;
            while (t>1&&calc(c[t],a[i])<calc(c[t-1],a[i])) t--;
            if (t==1&&a[i].y>c[t].y) c[t]=a[i]; else c[++t]=a[i];
        }
    }
}

int main(){
    cin >> n;
    for (int i=0;i<n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);
    cin >> m;
    for (int i=0;i<m;i++) scanf("%lld%lld",&a[i+n].x,&a[i+n].y),a[i+n].id=1+i;
    sort(a,a+n+m,cmp);
    for (int i=1;i<=m;i++) ans[i]=-1.0;
    solve();
    for (int i=0;i<n+m;i++) a[i].x*=-1,a[i].y*=-1;
    reverse(a,a+n+m); solve();
    for (int i=1;i<=m;i++) if (ans[i]<0) printf("No cross\n"); else printf("%.8f\n",ans[i]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 124ms, 内存消耗: 3940K, 提交时间: 2018-07-27 02:23:01

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point
{
	double x,y;
	int id;
}a[100010];
bool cmp(const point&aa,const point&bb)
{
	return aa.x<bb.x||(aa.x == bb.x&&aa.y<bb.y);
}
int stk[100010];
int n,m;
double xie(point aa,point bb)
{
	return (aa.y - bb.y)/(aa.x-bb.x);
}
double ans[1000010];
void solve1()
{
	int top = 0;
	for(int i=1;i<=m+n;i++)
	{
		if(!a[i].id)
		{
			while(top>1&&xie(a[stk[top-1]],a[stk[top-2]])-xie(a[stk[top-2]],a[i])<=1e-10)top--;
			stk[top++] = i;
		}
		else
		{
			if(top==0)continue;
			int l = 1,r = top;
			double res = xie(a[stk[0]],a[i]);
			while(r-l>1)
			{
				int mid = (l+r)>>1;
				if(xie(a[stk[mid]],a[i])<=xie(a[stk[mid-1]],a[i])){
					res = min(res,xie(a[stk[mid]],a[i]));
					l = mid;
				}
				else r = mid;
			}
			res = min(res,xie( a[stk[l]],a[i]));
			ans[a[i].id] = min(ans[a[i].id],res);
		}
	}
}
int main(int argc, char const *argv[])
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&a[i].x,&a[i].y);
		a[i].id = 0;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lf%lf",&a[i+n].x,&a[i+n].y);
		a[i+n].id = i;ans[i] = 1;
	}
	sort(a+1,a+1+n+m,cmp);
	solve1();
	reverse(a+1,a+n+1+m);
	solve1();
	for(int i=1;i<=m;i++)
	{
		if(ans[i]>1e-7)printf("No cross\n");
		else printf("%.10f\n",-ans[i] );
	}
	return 0;
}