题目大意：
在平面上有 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;
}
全部评论
(0) 回帖