任意兩點連成一天直線，現在有N個點，求斜率第k大的斜率
輸入n,k 及n個點的坐標：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void ssort(vector<int>x,vector<int>y,int len)
{
for( int i=0;i<len-1;i++)
{
for(int j=0;j<len-i-1;j++)
{
if(x[j]>x[j+1])
{
swap(x[j],x[j+1]);
swap(y[j],y[j+1]);
}
}
}
}
int getPartition(vector<int> &nums, int low, int height)
{
int keyVal = nums[height];
int i = low - 1;
for (int j = low; j < height; j++)
{
if (nums[j] >= keyVal)
{
i = i + 1;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[height]);
return i+1;
}
//迭代快排
void quicksot(vector<int> &nums,int low,int height) {
if (low<height)
{
int mid = getPartition(nums, low, height);
quicksot(nums, low, mid-1);
quicksot(nums, mid + 1, height);
}
}
int main()
{
int n,k;
cin>>n>>k;
vector<int> x;
vector<int> y;
vector<int> kk;
int result=0;
int t1,t2;
for(int i=0;i<n;i++)
{
cin>>t1>>t2;
x.push_back(t1);
y.push_back(t2);
}
cout<<x[2]<<y[2];
ssort(x,y,n);
for(int i1=0;i1<n;i1++)
{
for(int j1=i1+1;j1<n;j1++)
{
result=(y[j1]-y[i1])/(x[j1]-x[i1]);
cout<<result<<' ';
kk.push_back(result);
}
}
quicksot(kk,0,kk.size()-1) ;
cout<<kk[k-1]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/114997.html
標籤：C++ 語言