题目大意：
给n个人参加赛跑，给出某一时刻每个人的位置和速度（保证单向，速度恒定，且互不相同，且不为0），问，假如无限跑下去，过程中有可能有多少个不同的人领先过？（如果某一时刻两人同时领先，则都不算）
做法：
画成s-t图的话，很容易得出半平面交的做法，即以y轴和无穷远向这n条射线包围，求得围成的多边形内核上有多少条线段的问题（去掉y轴和无穷远）。
半平面交N^logN的我不会写，于是就用了himdd大神的模板，算法来源zzy大神的论文。
由于最后求得的点集可能有重点问题，需要先sort再unique一下去重。（表示这份代码用到了complex类，unique，distance等stl。。。太orz了）
代码：
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<complex>
#include<algorithm>
#include<cmath>
using namespace std;
const double inf=1e-10;
const int Max=60010;
typedef complex<
double> Point;
inline
int dbcmp(
double tp){
return tp<-inf?-1:tp>inf;}
double operator^(Point a,Point b)
{
return imag(conj(a)*b);}
struct Line{
Point a,b;
double angle;
Line(){}
Line(Point a,Point b):a(a),b(b){angle=arg(a-b);}
};
bool operator<(Line p,Line l){
return dbcmp(p.angle-l.angle)<0||
(dbcmp(p.angle-l.angle)==0&&dbcmp(p.b-p.a^l.b-p.a)<0);
}
Point
operator*(
const Line& u,
const Line&v)
{
Point tp=u.a;
double fz=u.a-v.a^v.b-v.a;
double fm=u.a-u.b^v.b-v.a;
return tp+(u.b-u.a)*fz/fm;
}
bool onleft(Point p,Line u)
{
return dbcmp(p-u.a^u.b-u.a)<=0;
}
bool uniquecmp(Line u,Line v)
{
int a = dbcmp(u.angle-v.angle)==0;
if(a)
puts("cao");
return a;
}
bool iter(Point p,Point q)
{
return dbcmp(real(p) - real(q)) < 0 || (dbcmp(real(p) - real(q)) == 0 && dbcmp(imag(p) - imag(q)) < 0);
}
Point p[Max];
Line l[Max];
int e[Max];
//line的下标
int get_kernel(Line *l,
int lsz,Point *p )
{
int eb=0,ee=2,pb=0,pe=1;
sort(l,l+lsz);
p[lsz]=p[0];
lsz=distance(l,unique(l,l+lsz,uniquecmp));
e[0]=0;e[1]=1;
p[0]=l[0]*l[1];
for(
int i=2;i<lsz;i++){
while(pb!=pe&&!onleft(p[pe-1],l[i]))pe--,ee--;
while(pb!=pe&&!onleft(p[pb],l[i]))pb++,eb++;
p[pe++]=l[i]*l[e[ee-1]];
e[ee++]=i;
}
while(pb!=pe&&!onleft(p[pe-1],l[e[eb]]))pe--,ee--;
//这个循环好像是没有用的。。
while(pb!=pe&&!onleft(p[pb],l[e[ee-1]]))pb++,eb++;
p[pe++]=l[e[pb]]*l[e[ee-1]];
int psz=pe-pb;
for(
int i=0;pb!=pe;i++)p[i]=p[pb++];
return psz;
//点的个数
}
bool uniqueccc(Point p,Point q)
{
return dbcmp(real(p)-real(q)) == 0 && dbcmp(imag(p)-imag(q))==0;
}
void gao()
{
int n;
int lsz=0;
scanf("%d",&n);
double x,y;
for(
int i=0;i<n;i++)
{
scanf("%lf%lf",&x,&y);
l[lsz++]=Line(Point(0,x),Point(1,x+y));
}
l[lsz++]=Line(Point(0,0),Point(1,0));
l[lsz++]=Line(Point(1e22,0),Point(1e22,1));
l[lsz++]=Line(Point(1,1e22),Point(0,1e22));
l[lsz++]=Line(Point(0,1e22),Point(0,0));
int psz=get_kernel(l,lsz,p);
sort(p,p + psz,iter);
psz = distance(p,unique(p,p + psz,uniqueccc));
printf("%d\n",psz-2);
}
int main()
{
int t;
scanf("%d",&t);
for(
int i = 0;i < t;i++)
gao();
}
另一个做法：
学自各种大牛的单调栈。
对于所有元素按照p进行从大到小的排序。因为初始时刻p最大的一定是解集元素之一，
所以虚拟一个元素（p与p最大值相同，速度为0），把这个虚拟元素和第一元素压入栈中，作为初始化。
然后对于之后的第i个元素，先判断它是否比所有已出现过的元素v都大，如果不大于，则直接跳过（因为p小，v同，肯定追不上），再之后就比较该元素追上栈顶下一个元素和栈顶元素追上栈顶下一个元素的时间，如果该元素时间短，就弹栈，直到出现>=为止，把该元素入栈。
最后栈中元素减一即为答案。
算法的原理在于，第一个元素肯定可以领先，然后就比较谁能更早的超过曾经领先过的元素，谁也就曾经“真的”领先过。
栈中元素保证了p单调非增，v单调增。维护出来的依旧是一个凸集，和半平面交效果相同。
有一个问题，很值得思考，这个做法对于所有约束条件符号完全相同的线性规划问题，是有通解性的吧？ax + by + c < 0，保证a，b，< 分别同号的情况下。
“维护单调性”。orz这个神想法。
附代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#include <algorithm>
#define maxn 50005
typedef
long long ll;
int t,n;
struct node
{
int p,v;
node(){}
node(
int _p,
int _v):p(_p),v(_v){}
}nn[maxn];
int ss[maxn];
bool operator < (node a,node b){
return a.p > b.p || (a.p == b.p && a.v < b.v);}
bool ok(node a,node b,node c)
{
return (ll) (b.p - c.p) * (ll) (a.v - b.v) <= (ll)(b.p - a.p) * (ll)(c.v-b.v);
}
void gao()
{
scanf("%d",&n);
int a,b;
for(
int i = 0;i < n;i++)
{
scanf("%d %d",&a,&b);
nn[i] = node(a,b);
}
sort(nn,nn + n);
int top = 1;
nn[n] = node(nn[0].p,0);
ss[0] = n;
ss[1] = 0;
int fuck = nn[0].v;
for(
int i = 1;i < n;i++)
{
if(nn[i].v < fuck)
continue;
fuck = nn[i].v;
while(top > 0 && ok(nn[ss[top]],nn[ss[top-1]],nn[i]))
top--;
ss[++top]=i;
}
printf("%d\n",top);
}
int main()
{
scanf("%d",&t);
for(
int i = 0;i < t;i++)
gao();
}