[luogu7340]Balance

构造一个坐标系，共有$n$个黑点和百点，第$i$个黑点为$(p_{i},a_{i})$，第$i$个白点为$(-q_{i},-b_{i})$

考虑第$i$个黑点和第$j$个白点连线的斜率，恰好就是$f(i,j)$

根据$p_{i},q_{i}>0$，注意到黑点一定在白点右侧，且恰好从$y$轴将两者分开

对于$f(i,j)$，若其是所有$f(i,k)$（$1\le k\le n$）中第$x$小，这也就等价于存在$x$个白点在第$i$个黑点和第$j$个白点连线的上方（包括线上）且严格在其上方的白点数小于$x$个

（对于这些白点，其与第$i$个黑点的连线斜率一定比第$j$个白点小）

类似地，$f(i,j)$是所有$f(k,j)$（$1\le k\le n$）中第$y$小，也就等价于存在$y$个黑点在第$i$个黑点和第$j$个白点连线的下方（包括线上）且严格在其下方的黑点数小于$y$个

从中，可以发现合法性仅与这条直线有关，且当直线确定后，从其上任取一个黑点和白点即为答案

（不难证明若其满足上述条件，则一定存在这样的黑点和白点）

从几何的角度来说，一个点$P$在直线$l$上方，等价于过$P$作与$l$平行的直线后其截距大于$l$的截距（如果允许在直线$l$上即后面变为大于等于）

当确定斜率后，过所有白点作一条该斜率的直线，也就是要找到与$y$轴交点上从上往下第$x$个交点，如果该斜率可行，那么必然是这条直线，然后我们检验另外一个条件即可

斜率是具备单调性的，具体来说，随着斜率的增长，这个截距也一定向上移动，那么直线下的黑点数也单调递增，即单调（特别的，相等时应令$r=mid$）

时间复杂度为$o(n\log n)$（具体实现可以利用nth_element函数），可以通过

（代码会挂掉，大概是因为浮点误差）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 500005

 4 #define eps 1e-6

 5 int t,n,x,y,a[N],b[N],p[N],q[N],id[N];

 6 double tmp;

 7 bool cmp(int x,int y){

 8     return q[x]*tmp-b[x]>q[y]*tmp-b[y];

 9 }

10 void read(int &x){

11     int flag=x=0;

12     char c=getchar();

13     while ((c<'0')||(c>'9')){

14         if (c=='-')flag=1;

15         c=getchar();

16     }

17     while ((c>='0')&&(c<='9')){

18         x=x*10+c-'0';

19         c=getchar();

20     }

21     if (flag)x=-x;

22 }

23 int get(double k){

24     tmp=k;

25     for(int i=1;i<=n;i++)id[i]=i;

26     nth_element(id+1,id+x,id+n+1,cmp);

27     return id[x];

28 }

29 int calc(double k){

30     int x0=get(k),ans=0;

31     double c=q[x0]*k-b[x0];

32     for(int i=1;i<=n;i++)

33         if (a[i]-k*p[i]<=c+eps)ans++;

34     return ans;

35 }

36 int main(){

37     read(t);

38     while (t--){

39         read(n),read(x),read(y);

40         for(int i=1;i<=n;i++)read(a[i]),read(b[i]),read(p[i]),read(q[i]);

41         double l=-2e9,r=2e9;

42         while (r-l>eps){

43             double mid=(l+r)/2;

44             if (calc(mid)>=y)r=mid;

45             else l=mid;

46         }

47         l=r;

48         int x0=get(l);

49         for(int i=1;i<=n;i++)

50             if (fabs((a[i]-l*p[i])-(q[x0]*l-b[x0]))<=eps){

51                 printf("%d %d\n",i,x0);

52                 break;

53             }

54     }

55 }

巴特西

[luogu7340]Balance

最新文章

热门文章