140C message
题目大意:
在平面上有 n 条直线 y=ax+b(a ≠ 0并且总是存在)。有 m 次询问,每次询问给出一条直线 y=cx+d(c ≠ 0并且总是存在),问已有的 n 条直线与这条询问线形成的交点中横坐标最大值是多少,如果没有交点则输出 "No cross"。
知识点: 凸包
解题思路:
由不难得出两条直线交点的横坐标为:。如果将 (a,b), (c,d) 看成是两个点的坐标,那么 x 等于这两个点的斜率的相反数,求 x 最大值就等价于求斜率的相反数的最大值,等价于求斜率的最小值。于是问题可以转化为:给定 n 个点的坐标,m 次询问,每次询问给出一个点,问这个点到 n 个点的斜率的最小值是多少。
不难想象出:对于询问点左边的点,斜率最小的点一定是在这些点的凸包上,可以想象出一条过询问点的直线,无论你顺时针还是逆时针扫描,对于询问点左边的点,你第一个遇到的点一定是凸包上的点。而且询问点相对于凸包上的点的斜率满足凸函数的性质,出题人的题解中介绍了一种二分找到斜率最小点的方法。
因此,对于询问点左边的点,可以维护一个凸包,然后二分找到最小的斜率。而对于询问点右边的点,可以将所有的坐标值都取反再求解一次,此时所有的点都左右颠倒了。
AC代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; const double esp=1e-10; const int MAXN=100000+5; struct Point{ int x,y,id; Point(int _x=0,int _y=0,int _id=0){ x=_x,y=_y,id=_id; } bool operator <(const Point &b)const{ if(x==b.x) return id<b.id; return x<b.x; } Point operator -(const Point &b)const{ return Point(x-b.x,y-b.y); } LL operator ^(const Point &b)const{ return 1ll*x*b.y-1ll*y*b.x; } }; int sgn(double x){ if(fabs(x)<esp) return 0; if(x<0) return -1; return 1; } double K(Point a,Point b){ return (double)(a.y-b.y)/(double)(a.x-b.x); } double res[MAXN]; struct ConvexHull{ double ans[MAXN]; int Stack[MAXN],top=0; Point p[MAXN]; void Graham(int n){ sort(p,p+n); for(int i=0;i<n;i++){ if(p[i].id){ if(top){ int l=0,r=top-1; while(l<r){ int m=(l+r)>>1; if(K(p[i],p[Stack[m]])<K(p[i],p[Stack[m+1]])) r=m; else l=m+1; } ans[p[i].id]=K(p[i],p[Stack[l]]); } else ans[p[i].id]=1; } else{ while(top>1&&((p[i]-p[Stack[top-2]])^(p[Stack[top-1]]-p[Stack[top-2]]))<=0) top--; Stack[top++]=i; } } } }c1,c2; int main(){ // freopen("in.txt","r",stdin); int n,m,x,y; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&x,&y); c1.p[i]=Point(x,y); c2.p[i]=Point(-x,-y); } scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); c1.p[n+i]=Point(x,y,i+1); c2.p[n+i]=Point(-x,-y,i+1); } c1.Graham(n+m); c2.Graham(n+m); for(int i=1;i<=m;i++) res[i]=-1.0*min(c1.ans[i],c2.ans[i]); for(int i=1;i<=m;i++){ if(res[i]<=0) puts("No cross"); else printf("%.10lf\n",res[i]); } return 0; }