P3256 [JLOI2013]赛车

· · 题解

题意描述：

有 n 辆汽车，每辆汽车有初始位置 k 和速度 v 。问你有多少车能在某一时刻跑在所有车的前面。

solution

我们把每辆车的位置关于时间的函数直线画出来，发现一辆车某一时刻能跑在所有车的前面，当且仅当他的函数直线是这几个一次函数交区域的一条边。

具体的证明，我不太会，反正结论猜对就ok了。

注意一下：每条直线的定义域是 (0,\infty), 所以我们只能在第一象限内做半平面交，一开始把四条边界直线加进去就好了。

然后我们就可以愉快的套半平面交的板子了。

就这样了，一道紫题就被我们水过去了？？？

你太 naive 了！

首先，这道题的值域为 (0,1e9) 这意味着我们求直线交点的时候可能会爆 10^{18}, 所以 lim 的上限要设大一点。

第二点：为了避免被卡精度，我们的 eps 要设的尽量小一些，尽量使用 long double。

第三点也是最重要的一点：有的车的函数直线可能完全相同，但我们做半平面交只会取一条直线，导致我们的答案出错（不少同学 WA 90 分可能就是这个原因）。

但好在这道题的数据范围只有 1e4, 所以我们完全可以到最后在扫一遍，看有没有少算的。

然后就没有什么注意的了，保证自己的板子没问题就行（自己一开始板子写错了，交了好几次才发现，淦）.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define double long double
const int N = 1e5+10;
const long long lim = 1e18+10;//lim设大点，eps设小点
const double eps = 1e-18;
int n,m,cnt,num,l,r,ans[N];
double k[N],w[N];
struct point
{
    double x,y;
    point(){}
    point(double a,double b){x = a, y = b;}
}sta[N];
typedef point Vector;
struct line
{
    int id;
    point x,y;
    double ang;
    line(){}
    line(point a,point b,int i)
    {
        x = a; y = b; id = i;
        ang = atan2(b.x-a.x,b.y-a.y);
    }
}q[N],L[N];
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}
point operator + (point a,point b){return point(a.x+b.x,a.y+b.y);}
point operator - (point a,point b){return point(a.x-b.x,a.y-b.y);}
point operator * (point a,double k){return point(a.x*k,a.y*k);}
double Dot(point a,point b){return a.x*b.x+a.y*b.y;}
double Cro(point a,point b){return a.x*b.y-a.y*b.x;}
double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool OnRight(point p,line a){return dcmp(Cro(p-a.x,a.y-a.x)-eps) >= 0;}
point Root_LL(line a,line b)//两直线的交点
{
    Vector v = a.y-a.x, u = b.y-b.x, w = a.x-b.x;
    double t = Cro(w,u)/Cro(u,v);
    return a.x + v * t;
}
bool comp(line a,line b)
{
    if(dcmp(a.ang-b.ang) == 0) return OnRight(b.x,a);
    return a.ang < b.ang;
}
int HPI()//半平面交板子
{
    l = 1, r = 1; q[1] = L[1];
    for(int i = 2; i <= cnt; i++)
    {
        if(dcmp(L[i].ang-L[i-1].ang) == 0) continue;
        while(l < r && OnRight(sta[r-1],L[i])) r--;
        while(l < r && OnRight(sta[l],L[i])) l++;
        q[++r] = L[i];
        if(l < r) sta[r-1] = Root_LL(q[r],q[r-1]);
    }
    while(l < r && OnRight(sta[r-1],q[l])) r--;
    while(l < r && OnRight(sta[l],q[r])) l++;
    sta[r] = Root_LL(q[l],q[r]);
    if(r-l+1 == 2) return 0;
    return r-l+1;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) cin>>w[i];
    for(int i = 1; i <= n; i++) cin>>k[i];
    point a = point(0,0); point b = point(lim,0);
    point c = point(lim,lim); point d = point(0,lim);
    L[++cnt] = line(a,b,0); L[++cnt] = line(b,c,0);//四条边界直线
    L[++cnt] = line(c,d,0); L[++cnt] = line(d,a,0);
    for(int i = 1; i <= n; i++) 
    {
        point a = point(0,w[i]); point b = point(1,k[i]+w[i]); 
        L[++cnt] = line(a,b,i);
    }
    sort(L+1,L+cnt+1,comp);
    m = HPI();
    for(int i = 1; i <= m; i++)//最后扫一遍，看有没有漏算的
    {
        for(int j = 1; j <= n; j++)
        {
            if(w[j] == w[q[i].id] && k[j] == k[q[i].id]) ans[++num] = j;
        }
    }
    sort(ans+1,ans+num+1);
    printf("%d\n",num);
    for(int i = 1; i <= num; i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}