【JZOJ6290】倾斜的线【计算几何】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/6290

---

思路：

以下令$k=frac{p}{q}$。
首先，画出对于每一个点斜率为$k$的直线，将这些点以斜率为$k$的截距排序。如下图。

此时我们假设存在三条有序点$x,y,z$，那么直线$xz$的斜率一定不是最接近$k$的。因为直线$xy,yz$中必然有一条的斜率大于$xz$，另外一条的斜率必然小于$xz$。那么直线$xz$的斜率最接近$k$当且仅当$xz$的斜率等于$k$。但是此时就一定有$x,z$两点排序后是相邻的，但是我们规定了中间必然夹着一个点$y$，所以$xz$的斜率也不可能为$k$。
例如下图，$x=2,y=3,z=5$

此时直线$xy$的斜率就小于直线$xz$的斜率，直线$yz$的斜率就大于直线$xz$的斜率。
同时，容易发现直线$xy$的斜率是相对于另外两条直线的斜率更加接近于$k$的。
归纳一下，一条直线可能为答案当且仅当该直线的端点编号相邻。
那么可能的直线就只有$n-1$条了，直接排序后暴力判断一下就可以了。

---

代码：

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=200010;
ll P,Q,p,q,GCD;
double k;
int n;

struct node
{
	double b;
	ll x,y;
}a[N];

bool cmp(node x,node y)
{
	return x.b<y.b;
}

int main()
{
	freopen("slope.in","r",stdin);
	freopen("slope.out","w",stdout);
	scanf("%d%lld%lld",&n,&P,&Q);
	k=(double)P/(double)Q;
	for (int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&a[i].x,&a[i].y);
		a[i].b=(double)a[i].y-k*(double)a[i].x;
	}
	sort(a+1,a+1+n,cmp);
	p=abs(a[1].y-a[2].y),q=abs(a[1].x-a[2].x);
	for (int i=2;i<n;i++)
	{
		double k1=(double)abs(a[i].y-a[i+1].y)/(double)abs(a[i].x-a[i+1].x);
		double k2=(double)p/(double)q;
		if (fabs(k1-k)<fabs(k2-k)) p=abs(a[i].y-a[i+1].y),q=abs(a[i].x-a[i+1].x);
			else if (fabs(k1-k)==fabs(k2-k) && k1<k2) p=abs(a[i].y-a[i+1].y),q=abs(a[i].x-a[i+1].x);
	}
	GCD=__gcd(q,p);
	printf("%lld/%lld",p/GCD,q/GCD);
	return 0;
}