题目传送：https://www.nowcoder.com/acm/contest/140/C
题意：有n个云层，每个云层可以表示为y=ax+b。每个飞机的航线可以表示为时间x时，坐标为(x,cx+d)。问飞机旅程与最后一个云层相交的x坐标。不存在
分析：
可以确定两直线联立后解得交点x=(b-d)/(a-c)。
可以看做是点（a,b）和（c,d）的斜率的负数。
要求的最大的x，那么就变成了求得最小的斜率，答案最后再乘-1即可。
就是求每个（c,d）点到（a,b）的斜率，可以把每一个（a,b）看成一个点，求凸包。
每碰到一个（c,d）二（san）分到凸包上的点的斜率。维护最小值。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const double eps=1e-8; 4 const double inf=1e20; 5 const int maxn=1e5+10; 6 int sgn(double x){ 7 if (fabs(x)<eps) return 0; 8 if (x<0) return -1; 9 return 1; 10 } 11 struct point{ 12 double x,y; 13 int id; double ans; 14 point(){} 15 point(double _x,double _y):x(_x),y(_y){} 16 point operator +(const point &b)const{ 17 return point(x+b.x,y+b.y); 18 } 19 point operator -(const point &b)const{ 20 return point(x-b.x,y-b.y); 21 } 22 double operator ^(const point &b)const{ 23 return x*b.y-y*b.x; 24 } 25 bool operator <(const point &b)const{ 26 if (sgn(x-b.x)==0) return y<b.y; 27 return x<b.x; 28 } 29 }; point p[maxn],pp[maxn]; 30 int n,m; 31 double calc(point a,point b){ 32 if (sgn(a.x-b.x)==0) return 1.0; 33 return (a.y-b.y)/(a.x-b.x); 34 } 35 double cross(point p,point a,point b){ 36 return (a-p)^(b-p); 37 } 38 void convex_hull(point p[],int N,point q[]){ 39 sort(p,p+N); 40 int m=0; 41 for (int i=0;i<N;i++){ 42 if (p[i].id>n){ 43 if (m==0) continue; 44 int l=0,r=m-1,mid; 45 while (l<r){ 46 mid=(l+r)>>1; 47 if (calc(p[i],q[mid])<calc(p[i],q[mid+1])){ 48 l=mid; 49 } 50 else r=mid-1; 51 } 52 p[i].ans=min(p[i].ans,calc(p[i],q[l])); 53 } 54 else{ 55 while (m>1 && cross(q[m-2],q[m-1],p[i])<=0) m--; 56 q[m++]=p[i]; 57 } 58 } 59 int k=m; 60 for (int i=N-2;i>=0;i--){ 61 if (p[i].id>n){ 62 if (m==k) continue; 63 int l=0,r=m-1,mid; 64 while (l<r){ 65 mid=(l+r)>>1; 66 if (calc(p[i],q[mid])<calc(p[i],q[mid+1])){ 67 l=mid; 68 } 69 else r=mid-1; 70 } 71 p[i].ans=min(p[i].ans,calc(p[i],q[l])); 72 } 73 else{ 74 while (m>k && cross(q[m-2],q[m-1],p[i])<=0) m--; 75 q[m++]=p[i]; 76 } 77 } 78 } 79 bool cmp(point a,point b){ 80 return a.id<b.id; 81 } 82 int main(){ 83 cin >> n; 84 for (int i=0;i<n;i++){ 85 cin >> p[i].x >> p[i].y; 86 p[i].id=i+1; p[i].ans=inf; 87 } 88 cin >> m; 89 for (int i=n;i<n+m;i++){ 90 cin >> p[i].x >> p[i].y; 91 p[i].id=i+1; p[i].ans=inf; 92 } 93 convex_hull(p,n+m,pp); 94 for (int i=0;i<n+m;i++){p[i].x*=-1; p[i].y*=-1;} 95 convex_hull(p,n+m,pp); 96 sort(p,p+n+m,cmp); 97 for (int i=n;i<n+m;i++) 98 if (p[i].ans>=0) cout << "No cross "; 99 else printf("%.7f ",-p[i].ans); 100 return 0; 101 }