题意这样的
有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