自动搬运

查看原文

来自洛谷，原作者为

	Y_zhao111 This person is too lazy to leave anything.

搬运于2025-08-24 22:22:26，当前版本为作者最后更新于2024-08-22 13:53:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

You can go and read the English version of this solution.

Description

题目传送门：P6614 蛋糕 Cake。

自己构造出一个一次函数，要求将平面上的 $n$ 个点分成 $a:b$ 两部分。

Analysis

考虑极端情况。

以一个 斜率不小于 $1$ ，不大于 $10^{12}$ 的一次函数图像 为轮廓在蛋糕上划一刀。

极端数据 $k={10}^{12}$，那么函数就相当于一条平行于纵轴的直线，如下图。

所以我们只需要让左边满足 $n\times \dfrac{a}{a+b}$ 个，右边满足 $n\times \dfrac{b}{a+b}$ 即可。

化简一下就是左 $\dfrac{n\times a}{a+b}$，右 $\dfrac{n\times b}{a+b}$。

由于本题采用 $\text{Special Judge}$，输出唯一合法解即可。

设左边的点数为 $A$，右边的点数为 $B$。

$k={10}^{12}$，$x_0=x_A,y_A$ 一定是一组合法解。

Code

#include <bits/stdc++.h>
using namespace std;


const long long K = (long long)(pow(10 , 12));

struct Node
{
	int x , y;
	
	inline bool operator < (const Node &cmp) const //随个人喜好，也可以写成 cmp()
	{
		return x != cmp.x ? x < cmp.x : y > cmp.y;
	}
	
}Cake[1000005];

signed main()
{
	int n , a , b;
	cin >> n >> a >> b;
	
	for(register int i = 1 ; i <= n ; i ++)
	{
		cin >> Cake[i].x >> Cake[i].y;
	}
	
	sort(Cake + 1 , Cake + n + 1);
	cout << K << " " << Cake[n * a / (a + b)].x << " " << Cake[n * a / (a + b)].y << endl;
	return 0;
}