自动搬运

查看原文

来自洛谷，原作者为

	双管荧光灯 楽園(はめつ)への花道をいざ照らせ

搬运于2025-08-24 22:28:56，当前版本为作者最后更新于2021-02-13 12:39:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们发现这个分式很像一个斜率，但是后面是正号，而斜率是 $\frac{y1-y2}{x1-x2}$ ，因此我们对b和q数组取它们的相反数，我们就得到了 $2n$ 个点。

我们把一半染红，坐标 $(p_i,a_i)$ ，另一半我们染蓝， 坐标 $(-q_i,-b_i)$ ，$(i,j)$ 的值就可以被描述为红点 $i$ 和 蓝点 $j$ 之间的斜率了。而 $(i,j)$ 的排名可以根据 $(i,j)$ 这条直线上方的蓝点数，与这条直线下方的红点数算出。

于是我们找这条直线即可，我们设其截距为 $z$ ，如果我们知道截距，那么就能找到逆时针方向第 $y$ 个红点，它一定是这条直线上的点，于是这条直线就确定下来了。我们发现 $(0,z)$ 与第 $y$ 个红点的连线上方的蓝点数随着 $z$ 的增大是单调不升的。于是我们可以二分 $z$ 进行判断。

找第 $y$ 个红点可以使用 nth_element ，这样复杂度就是 $O(n\log(eps^{-1}))$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=1000005,M=998244353,E=262144;
#define __float128 long double
__float128 eps=0.000000002;
int r,i,n,ans,p,j,k,f[N],x,y,t;
__float128 C;
struct str{
	int x,y,id;
}a[N],b[N];
bool flag;
bool cmp(str a,str b)
{
	return a.x*(b.y-C)-(a.y-C)*b.x>0;
}
__float128 Fabs(__float128 M)
{
	return M<0?-M:M;
}
int check(__float128 m)
{
	C=m;
	nth_element(a+1,a+y,a+1+n,cmp);
	int s1=0,s2=0;
	for(i=1;i<=n;++i)
		if(Fabs(a[y].x*(b[i].y-C)-(a[y].y-C)*b[i].x)/max(a[i].x,a[i].y)<eps)
			++s2;
		else
			if(a[y].x*(b[i].y-C)-(a[y].y-C)*b[i].x>0)
				++s1;
	if(s1<x&&s1+s2>=x)
	{
		flag=true;
		for(i=1;i<=n;++i)
			if(Fabs(a[y].x*(b[i].y-C)-(a[y].y-C)*b[i].x)/max(a[i].x,a[i].y)<eps)
			{
				printf("%d %d\n",a[y].id,i);
				break;
			}
	}
	return s1;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d %d",&n,&x,&y);
		for(i=1;i<=n;++i)
		{
			scanf("%d %d %d %d",&a[i].y,&b[i].y,&a[i].x,&b[i].x);
			b[i].x=-b[i].x,b[i].y=-b[i].y;
			a[i].id=i,b[i].id=i;
		}
		flag=false;
		__float128 l=-1000000000,r=1000000000;
		while(r-l>0.0000000002)
		{
			__float128 mid=(l+r)/2;
			if(check(mid)<x)
				r=mid;
			else
				l=mid;
			if(flag)
				break;
		}
		if(!flag)
			puts("0 0");
	}
}