Description

平面上有N個點，任意2個點確定一條直線，求出所有這些直線中，斜率最大的那條直線所通過的兩個點。
（點的編號為1-N，如果有多條直線斜率相等，則輸出所有結(jié)果，按照點的X軸坐標(biāo)排序，正序輸出。數(shù)據(jù)中所有點的X軸坐標(biāo)均不相等，且點坐標(biāo)為隨機。）

Input

第1行，一個數(shù)N，N為點的數(shù)量。(2 <= N <= 10000)
第2 - N + 1行：具體N個點的坐標(biāo)，X Y均為整數(shù)(-10^9 <= X,Y <= 10^9)

Output

每行2個數(shù)，中間用空格分隔。分別是起點編號和終點編號（起點的X軸坐標(biāo) < 終點的X軸坐標(biāo)）

Input示例

5
1 2
6 8
4 4
5 4
2 3

Output示例

4 2

Solution

• 貪心：先按這 N 個點按 x 排序，找相鄰兩個比較即可。

• 為什么呢？假設(shè)三個點排序后順序是ABC，那么有兩種情況：

• ABC共線，則 k(AB)=k(BC)=k(AC) ；

• ABC不共線，則ABC將形成一個三角形，那么 k(AC)<Max(k(AB),k(BC)) 。

• 說明跨點的一定不會比相鄰的更優(yōu)，貪心地找是正確的。時間復(fù)雜度 O(N?log?N) 。

• 統(tǒng)計答案時也是，用鏈表存著共線的點，

• 新加入一個點，如果也共線，就從鏈表中逐個匹配，再將自己也加入鏈表中。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=10001; typedef pair<int,int> PI; int num; int next[N],rk[N]; PI a[N],f[N]; double ans=-1e9; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline double get(int x,int y) {return (a[x].second-a[y].second)*1.0/(a[x].first-a[y].first); } inline bool cmp(int x,int y) {return a[x].first<a[y].first; } int main() {int n=read();for(int i=1;i<=n;i++) a[rk[i]=i].first=read(),a[i].second=read();sort(rk+1,rk+1+n,cmp);for(int i=1;i<n;i++){double x=get(rk[i],rk[i+1]);if(x>ans){ans=x;f[num=1]=make_pair(rk[i],rk[i+1]);memset(next,0,sizeof(next));next[rk[i+1]]=rk[i];}elseif(x==ans){for(int j=next[rk[i]];j;j=next[j])f[++num]=make_pair(j,rk[i+1]);}}for(int i=1;i<=num;i++)if(a[f[i].first].first>a[f[i].second].first) swap(f[i].first,f[i].second);for(int i=1;i<=num;i++) printf("%d %d\n",f[i].first,f[i].second);return 0; }

總結(jié)

以上是生活随笔為你收集整理的51Nod 斜率最大的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。