平面上有N个点,任意2个点确定一条直线,求出所有这些直线中,斜率最大的那条直线所通过的两个点。
(点的编号为1-N,如果有多条直线斜率相等,则输出所有结果,按照点的X轴坐标排序,正序输出。数据中所有点的X轴坐标均不相等,且点坐标为随机。)
Input
第1行,一个数N,N为点的数量。(2 <= N <= 10000) 第2 - N + 1行:具体N个点的坐标,X Y均为整数(-10^9 <= X,Y <= 10^9)
Output
每行2个数,中间用空格分隔。分别是起点编号和终点编号(起点的X轴坐标 < 终点的X轴坐标)
Input示例
5 1 2 6 8 4 4 5 4 2 3
Output示例
4 2
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#define ll long long int
const int INF=0x3f3f3f3f;
using namespace std;
struct head
{
int x,y,c; //c用来记录是第几个点
}a[10000];
bool cmp(head x,head y)
{
if(x.x==y.x)
return x.y<y.y;
return x.x<y.x;
}
int main()
{
int aa=0,bb=0;
int cc=0;
int m;
cin>>m;
for(int i=0;i<m;i++)
{
cin>>a[i].x>>a[i].y;
if(i!=0)
a[i].c=a[i-1].c+1;
}
sort (a,a+m,cmp);
double max=-100000;
for(int i=1;i<=m;i++)
{
double n = ((double)a[i].y-a[i-1].y)/((double)a[i].x-a[i-1].x);
if(max>n)
{
max=max;
}else
{
max=n;
aa=a[i].c;
bb=a[i-1].c;
}
}
cout<<bb+1<<' '<<aa+1<<endl;
return 0;
}