如果把每个人的运动都画在一张s-t图上，则原问题可以转化为半平面交
当然，这里可以不用写成半平面交
直接对初始位置pi从大到小排序。添加一个虚拟的人，他和最前面的人位置一样，速度为0，并把它和最前面的人压入栈中。
考虑第k个人时，首先必须保证k的速度比前面k-1个人都快，否则不予考虑。假设栈中最后两个人分别是x和y，如果k追上x的时间小于等于y追上x的时间，则y出栈。然后把k压入栈中。
最后栈中的人（不算虚拟的）即为能领先的人，时间复杂度O(nlogn)
实现时要注意2个人初始位置相同的情况。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
struct point
{ int p,v; }a[50005];
bool cmp(const point &a,const point &b)
{ return a.p>b.p; }
bool check(const point &a,const point &b,const point &c)
{
return (long long)(a.p-c.p)*(b.v-a.v)<=(long long)(a.p-b.p)*(c.v-a.v);
}
int s[50005];
int main(void)
{
int u,n,maxv,i,t;
scanf("%d",&u);
while(u--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].p,&a[i].v);
sort(a+1,a+n+1,cmp);
a[0].p=a[1].p; maxv=a[0].v=0;
s[0]=0; s[1]=1; t=2;
for(i=2;i<=n;i++)
{
if (a[i].v<maxv) continue;
maxv=a[i].v;
while(t>1&&check(a[s[t-2]],a[s[t-1]],a[i])) t--;
s[t++]=i;
}
printf("%d\n",t-1);
}
return 0;
}
posted on 2010-10-13 12:33
zxb 阅读(635)
评论(2) 编辑 收藏 引用