test20180922 倾斜的线

时间：2021-11-17 20:58:17

题意

问题描述

给定两个正整数P和Q。在二维平面上有n个整点。现在请你找到一对点使得经过它们的直线的斜率在数值上最接近P/Q（即这条直线的斜率与P/Q的差最小），请输出经过它们直线的斜率p/q。如果有两组点的斜率的接近程度相同，请输出较小的斜率。保证答案的p/q > 0，即输出的p和q都是正整数。

输入格式

输入文件名为slope.in。

第一行三个正整数n P Q。

接下来n行每行两个正整数x y表示一个点的坐标。保证不存在x坐标相同或者y坐标相同的点（即斜率不会为无穷大与0）。

输出格式

输出文件名为slope.out。

输出仅一行，格式为p/q，表示最接近的斜率，其中p和q都是正整数。

样例输入

6 15698 17433

112412868 636515040

122123982 526131695

58758943 343718480

447544052 640491230

162809501 315494932

870543506 895723090

样例输出

193409386/235911335

分析

\[|\frac{y_1-y_2}{x_1-x_2}-\frac{P}{Q}|\\
=|\frac{(y_1Q-x_2P)-(y_2Q-x_2P)}{x_1Q-x_2Q}|
\]

然后就是斜率绝对值最小问题，是斜率最大的对偶问题。

按纵坐标排序即可。

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const ll INF=1e18;

const int MAXN=2e5+7;

int n;

ll P,Q;

struct node

{

	ll x,y;

	int id;

	bool operator<(const node&rhs)const

	{

		return y<rhs.y;

	}

	double operator/(const node&rhs)

	{

		return (double)(rhs.y-y)/(double)(rhs.x-x);

	}

}origin[MAXN],pnt[MAXN];

int gcd(int x,int y)

{

	return y==0?x:gcd(y,x%y);

}

int main()

{

  freopen("slope.in","r",stdin);

  freopen("slope.out","w",stdout);

	read(n);read(P);read(Q);

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

	{

		int x,y;

		origin[i].x=read(x);origin[i].y=read(y);

		pnt[i].id=i;

		pnt[i].y=(ll)y*Q-(ll)x*P;

		pnt[i].x=(ll)x*Q;

	}

	sort(pnt+1,pnt+n+1);

	double del=INF;

	int ans;

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

	{

		if(abs(pnt[i]/pnt[i+1])<del)

			ans=i,del=abs(pnt[i]/pnt[i+1]);

		else if(abs(pnt[i]/pnt[i+1])==del)

		{

			ans=(origin[pnt[ans+1].id]/origin[pnt[ans].id]<origin[pnt[i+1].id]/origin[pnt[i].id])?ans:i;

		}

	}

	int p=origin[pnt[ans+1].id].y-origin[pnt[ans].id].y,q=origin[pnt[ans+1].id].x-origin[pnt[ans].id].x;

	p=abs(p),q=abs(q);

	int g=gcd(p,q);

	printf("%d/%d\n",p/g,q/g);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

相关文章