一起来看流星雨 解题报告

这个题目其实就是求一个最远点对，然后在求最小的最远点对距离，对于求最远点对的问题，我们显然可以用旋转卡壳来做，即先求出所给流星坐标点所形成的凸包，很明显最远的点对只能出现在凸包上，求出凸包之后，我们选择能刚好卡住凸包的两条平行线，然后根据卡住的点对来更新最大值，这样旋转一圈就可以得到最大值（即旋转卡壳算法）。我们求出最远点对之后，在去考虑最远点对在什么时刻最小，这个时候我们可以根据时刻进行三分找最小值，最后求一下最小值即可。 （暴力三分不可取，因为暴力三分复杂度O(n^2logn)，显然会超时。。。所以必须采用旋转卡壳）
求凸包复杂度O(nlogn)
旋转卡壳复杂度O(n)
三分复杂度O(nlogn)
总的时间复杂度： O(nlogn^2)
额外空间复杂度： O(n)

代码：

const double eps = 1e-9;
int double_cmp(double x){
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1;
    return -1;
}

struct Point_{
    double x, y, vx, vy;
    int id;
    Point_() {}
    Point_ (double _x, double _y, int i):x(_x),y(_y),id(i) {}
    bool operator <(const struct Point_ &tmp)const {
        if(double_cmp(x-tmp.x) == 0) return double_cmp(y-tmp.y) < 0;
        return double_cmp(x-tmp.x) < 0;
    }
    bool operator == (const struct Point_ &tmp)const {
        return double_cmp(x-tmp.x)==0&&double_cmp(y-tmp.y)==0;
    }
} a[10005],st[10005],b[10005];
double XMulti(Point_ a, Point_ b, Point_ c)///ac X ab
{
    return (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y);
}

double dis(Point_ a, Point_ b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double dot(Point_ a, Point_ b, Point_ c)///点积 ab . ac
{
    double s1 = b.x-a.x;
    double t1 = b.y-a.y;
    double s2 = c.x-a.x;
    double t2 = c.y-a.y;
    return s1*s2 + t1*t2;
}

int ConvexHull(Point_ *p, int n, Point_ *st)//凸包
{
    sort(p, p+n);
    n = unique(p, p+n)-p;//去重
    int m = 0;
    for(int i=0; i<n; i++) {
        while(m>1 && XMulti(st[m-2],p[i],st[m-1])<=0)
            m--;
        st[m++] = p[i];
    }
    int k = m;
    for(int i=n-2; i>=0; i--) {
        while(m>k && XMulti(st[m-2],p[i],st[m-1])<=0)
            m--;
        st[m++] = p[i];
    }
    if(n > 1) m--;
    return m;
}
double rotating_calipers(Point_ *p, int n)//旋转卡壳求凸包的直径，平面最远的点对
{
    int k=1;
    double ans = 0;
    p[n]=p[0];
    for(int i=0; i<n; i++) {
        while(fabs(XMulti(p[i+1],p[k],p[i]))<fabs(XMulti(p[i+1],p[k+1],p[i])))
            k=(k+1)%n;
        ans = max(ans,max(dis(p[i],p[k]),dis(p[i+1],p[k])));
    }
    return ans;
}
int n, m;
double f(double t){
    for(int i=0; i<n; i++){
        b[i].x = a[i].x+t*a[i].vx;
        b[i].y = a[i].y+t*a[i].vy;
    }
    m = ConvexHull(b, n, st);
    double mx = rotating_calipers(st, m);
    return mx;
}
double sanfen(double l, double r){
    double midl, midr;
    while(r-l>eps){
        midl = l+(r-l)/3;
        midr = r-(r-l)/3;
        if(f(midl) >= f(midr)) l = midl;
        else r = midr;
    }
    return midl;
}
class Solution {
public:
    /**
     *
     * @param n int整型 流星个数
     * @param star int整型vector<vector<>> 流星坐标点和速度向量
     * @return double浮点型
     */
    double solve(int nn, vector<vector<int> >& star) {
        // write code here
        n = nn;
        for(int i=0; i<n; i++) {
            a[i].x = star[i][0];
            a[i].y = star[i][1];
            a[i].vx = star[i][2];
            a[i].vy = star[i][3];
        }
        double ans = sanfen(0, 1000000);
        return f(ans);
    }
};