題目鏈接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1112
題意：中文題誒～
思路：對於函數 f(x) = a + kx，對於x足夠大的情況下，顯然f(x)的值的相對大小是只受 k 影響的．對於 n 條這樣的直線最多可以發生 (n-1)*n/2 次超越；
不過本題只要求輸出前 1e4 次超越，所以可以先二分出1e4次超越的時間點(這部分是用來優化常數的)，然後再枚舉每一次超越即可．這樣的時間復雜
度爲 O(n^2)，對於 1e4 的數據量只要常數小一點還是能過的．．．
代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std; const int MAXN = 1e4+;
const int inf = 1e4;
pair<int, int> p[MAXN];//存儲開始時的數據
pair<int, int> p1[MAXN];//存儲1e4時間點的數據
pair<double, pair<int, int> > p2[MAXN*];//存儲答案
int vis[MAXN*], n; int get_times(int mid){ //計算在k時間點可以達到的超越次數
int ans = ;
for(int i=; i<n; i++){
p1[i].first = p[i].first + p[i].second * mid;
p1[i].second = i;
}
sort(p1, p1+n);
for(int i=; i<n; i++){
if(p1[i].second < i){
ans += i-p1[i].second;
}
}
return ans;
} void get_time(void){ //二分出達到1e4次超越的時間點
int l=, r=MAXN*;
int ans=;
while(l < r-){
int mid = (l+r)>>;
int cnt = get_times(mid);
if(cnt == inf) break;
else if(cnt > inf) r = mid;
else l = mid;
}
} int main(void){
scanf("%d", &n);
for(int i=; i<n; i++){
scanf("%d%d", &p[i].first, &p[i].second);
vis[p[i].first] = i+;
}
sort(p, p+n);
get_time();
int indx=;
for(int i=; i<n; i++){
int a2 = p[p1[i].second].first;
for(int j=; j<i; j++){
int a1 = p[p1[j].second].first;
if(a1 > a2){
int b1 = p[p1[j].second].second;
int b2 = p[p1[i].second].second;
double k = (a1-a2)*1.0/(b2-b1); //本次超越的時間點
p2[indx].first = k;
p2[indx].second.first = vis[a2];
p2[indx++].second.second = vis[a1];
}
}
}
if(!indx){
printf("No Solution\n");
}else{
sort(p2, p2+indx);
int cnt = min(indx, inf);
for(int i=; i<cnt; i++){
printf("%d %d\n", p2[i].second.first, p2[i].second.second);
}
}
return ;
}