本文共 1863 字，大约阅读时间需要 6 分钟。

题目

题解

题意

在$x$轴和$y$的正半轴上各有$n$个点

这$2n$个点要练成$n$条线段，要求任意两条线段不相交 有$m$个询问，每次询问给出点$P(x,y)$ 问线段OP与多少条线段相交（$O$为原点$(0,0)$）

分析

既然要求线段两两不相交

那么分别把$x$轴上的和$y$轴上的点从小到大排序，这样就可以满足线段两两不相交 我们可以求出每条线段的一次函数解析式（不会一次函数的送你一程：） 对于一条直线$(x1,y1),(x2,y2)$ 我们可以求出 $$\begin{gathered} k=\frac{y1-y2}{x1-x2} \\ b=\frac{y1+y2-k(x1+x2)}{2} \end{gathered}$$ 其实可以根据本题题目略加优化，请读者自行思考 对于每个询问 先求出询问的直线$OP$的解析式 然后找到一个最大的$k$ 使得直线$k$和直线$OP$的交点在线段$OP$上 求交点 现在我们有两个一次函数解析式 $\{\begin{array}{l}y=k1x+b1\\ y=k2x+b2\end{array}$ 在这个方程组中，$k1,k2,b1,b2$都是已知的 就可以求解 $\{\begin{array}{l}x=\frac{b2-b1}{k1-k2}\\ y=\frac{(k1+k2)x+b1+b2}{2}\end{array}$ 代入求解即可（其实可以根据本题题目略加优化，请读者自行思考） 求出交点之后，判断与点$P$的关系 如果在点$P$的右上角，说明不与当前直线相交，否则则相交 二分求出即可

Code

#include
   
    #include
    
     using namespace std;int n,m,i,l,r,mid,xx,yy,ans,x[100005],y[100005],b[100005];double k[100005];bool pd(int x){   	double x1,y1,kk;	kk=1.0*yy/xx;	x1=b[x]/(kk-k[x]);	y1=x1*kk;	if (x1<=xx&&y1<=yy) return true;	else return false;}int main(){   	freopen("T3.in","r",stdin);	freopen("T3.out","w",stdout);	scanf("%d",&n);	for (i=1;i<=n;i++)		scanf("%d",&x[i]);	for (i=1;i<=n;i++)		scanf("%d",&y[i]);	sort(x+1,x+n+1);	sort(y+1,y+n+1);	for (i=1;i<=n;i++)	{   		b[i]=y[i];		k[i]=-1.0*y[i]/x[i];	}	scanf("%d",&m);	for (i=1;i<=m;i++)	{   		scanf("%d%d",&xx,&yy);		l=1;		r=n;		ans=0;		while (l<=r)		{   			mid=(l+r)>>1;			if (pd(mid)==true) 			{   				l=mid+1;				ans=mid;				}				else r=mid-1;		}		printf("%d\n",ans);	} 	fclose(stdin);	fclose(stdout);	return 0;}
    
   

转载地址：http://gqql.baihongyu.com/