題意這樣的
有N架飛船，給出他們的起始位置和速度（速度為正數），求
(1)在比賽過程中它們會相遇多少次
(2)輸出排名前10000次的相遇事件
首先先畫畫s-v圖來看，如果按照s遞增的順序來添加直線，那么第i條直線與第j條直線(j<i)能相交的充要條件是v
j>v
i，這樣子就很簡單了，用任何一種樹結構維護前i條直線的v值，添加第i條直線時產生的相交個數就是v
j>v
i的直線條數。我是通過離散化+樹狀數組來做的，本想用set，沒想到iterator 不能相減求個數。。囧
第二問做的時候各種NC錯誤，各種NC想法，耗費了大概6個小時。。無語。。
其實就是多條線段求交點的掃描線法的變通。
維護一個堆和Hash表（判重），我偷懶，直接用set
里面存儲的是相鄰兩條直線相交的時刻，每次取出一次事件后更新下排名表和位置表，然后再將新產生的兩個相鄰的直線添加入set。
NC錯誤一：為了消除浮點比較誤差，將分數通分移項，沒考慮乘法時已溢出int。。。NC錯誤二：更新排名表和位置表的時候，竟然十分詭異地用swap交換兩個排名表中的項。。。。應該是先交換位置表中的項，再更新排名表。解釋下，位置表就是你排第幾，排名表是排第幾的是誰細心啊細心。。。無語
貼代碼
1 # include <cstdio>
2 # include <algorithm>
3 # include <cstring>
4 # include <set>
5 # define N 250005
6 using namespace std;
7 # define lowbit(t) ((t)&-(t))
8 struct node
9 {
10 int x,v,id;
11 }data[N];
12 int n;
13 bool cmpv(const node &a,const node &b)
14 {
15 return a.v<b.v;
16 }
17 bool cmpx(const node &a,const node &b)
18 {
19 return a.x<b.x;
20 }
21 int arr[N],table[N],ranklist[N];
22 void add(int pos)
23 {
24 while(pos<=n)
25 {
26 arr[pos]++;
27 pos+=lowbit(pos);
28 }
29 }
30 int sum(int pos)
31 {
32 int res=0;
33 while(pos>0)
34 {
35 res+=arr[pos];
36 pos-=lowbit(pos);
37 }
38 return res;
39 }
40
41 struct cmp
42 {
43 bool operator()(const pair<int,int> &a,const pair<int,int> &b) const
44 {
45 if(((long long)data[a.second].x-data[a.first].x)*(data[b.first].v-data[b.second].v)!=((long long)data[b.second].x-data[b.first].x)*(data[a.first].v-data[a.second].v))
46 return ((long long)data[a.second].x-data[a.first].x)*(data[b.first].v-data[b.second].v)<((long long)data[b.second].x-data[b.first].x)*(data[a.first].v-data[a.second].v);
47 else
48 return ((long long)data[a.first].x*(data[a.first].v-data[a.second].v)+data[a.first].v*(data[a.second].x-data[a.first].x))*(data[b.first].v-data[b.second].v)<
49 ((long long)data[b.first].x*(data[b.first].v-data[b.second].v)+data[b.first].v*(data[b.second].x-data[b.first].x))*(data[a.first].v-data[a.second].v);
50 }
51 };
52 set<pair<int,int>,cmp> q;
53 int main()
54 {
55 scanf("%d",&n);
56 for(int i=0;i<n;i++)
57 scanf("%d%d",&data[i].x,&data[i].v);
58 sort(data,data+n,cmpv);
59 data[0].id=1;
60 for(int i=1;i<n;i++)
61 data[i].id=(data[i].v==data[i-1].v?data[i-1].id:data[i-1].id+1);
62 sort(data,data+n,cmpx);
63 memset(arr,0,sizeof(arr));
64 int ans=0;
65 for(int i=0;i<n;i++)
66 {
67 ans=(ans+i-sum(data[i].id))%1000000;
68 add(data[i].id);
69 ranklist[i]=table[i]=i;
70 }
71 printf("%d\n",ans);
72 for(int i=1;i<n;i++)
73 if(data[i].v<data[i-1].v)
74 q.insert(make_pair<int,int>(i-1,i));
75 for(int i=1;i<=10000&&!q.empty();i++)
76 {
77 pair<int,int> top=*q.begin();
78 q.erase(q.begin());
79 printf("%d %d\n",min(top.first,top.second)+1,max(top.first,top.second)+1);
80 swap(table[top.first],table[top.second]);
81 ranklist[table[top.first]]=top.first;
82 ranklist[table[top.second]]=top.second;
83 if(table[top.first]!=n-1&&data[top.first].x<data[ranklist[table[top.first]+1]].x&&data[top.first].v>data[ranklist[table[top.first]+1]].v&&cmp()(top,make_pair<int,int>(top.first,ranklist[table[top.first]+1])))
84 q.insert(make_pair<int,int>(top.first,ranklist[table[top.first]+1]));
85 if(table[top.second]!=0&&data[ranklist[table[top.second]-1]].x<data[top.second].x&&data[ranklist[table[top.second]-1]].v>data[top.second].v&&cmp()(top,make_pair<int,int>(ranklist[table[top.second]-1],top.second)))
86 q.insert(make_pair<int,int>(ranklist[table[top.second]-1],top.second));
87 }
88 return 0;
89 }
90