题解 P7340 【『MdOI R4』Balance】

· · 题解

我们发现这个分式很像一个斜率，但是后面是正号，而斜率是 \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");
    }
}