题解 | #牛牛组数#

基本是抄了别人的算法，但有一点改进:
显然两颗星星之间的距离d关于时间t的函数d(t)是一个下凸函数，因而最小值唯一，从t=0开始逐步搜索的话，那么在遇到某个t满足d(t+1)≥d(t)的情况就可以终止本轮搜索，此时有d(t+1)≥d(t)>d(t-1)。根据下凸函数的特性，最小值一定属于区间(t-1,t+1)，因此可以使用更小的步长在这一区间进行下一轮搜索。
因此原来算法设定某个上界的做法既可能不妥（这个上界并不好直观估计），也无必要（出现目标函数下降趋势的终止就可以进入下一轮更高精度的搜索了），改进之后时间复杂度也有显著地提升。
考虑到坐标值最大为10^5，速度值最小为10^-3，那么搜索用的时间步长，初始值可取10^8的一半10^4，平衡一下搜索次数和时间步长的数量级。取较大的初始步长，也可以避免精确解对应的时间量级较大时，较小初始步长第一轮搜索太慢。
快速提高精度、缩小搜索范围、减少循环次数的做法，可能第一时间会想到的是二分查找、割线法之类的，但是因为确定精度还需公式计算比较麻烦，代码可能不如这种“十”分查找简单。但是可以考虑改为第二轮起以t为中心向两侧扩散查找，直观上平均复杂度应该可以再降低一半，就是写循环又会麻烦一点，有兴趣的可以自行实现比较效率。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 流星个数
     * @param star int整型vector<vector<>> 流星坐标点和速度向量
     * @return double浮点型
     */
    static const int N = 10004;


    int top, nP; //top is top of S
    struct mPoint {
        double x=0,y=0;
    };
    vector<mPoint> P,S;

    static bool cmp(const mPoint &a, const mPoint &b) {
        if (a.y==b.y) return a.x<b.x;
        else return a.y<b.y;
    }
    double Cross(const mPoint &p1, const mPoint &p2, const mPoint &p3, const mPoint &p4) {
        return (p4.y-p3.y)*(p2.x-p1.x) - (p2.y-p1.y)*(p4.x-p3.x);
    }
    bool cmp2(const mPoint &p1, const mPoint &p2) {
        double C = Cross(P[0], p1, P[0], p2);
        return C? C>0: SqDistance(P[0], p1)<SqDistance(P[0], p2);
    }
    void FindConvexHull() {
        auto it = min_element(P.begin(), P.end(), cmp);
        //swap(P[0], *it);
        auto tmp=P[0];
        P[0] = *it;
        *it = tmp;
        //sort
        auto mycmp = bind(&Solution::cmp2,this,placeholders::_1,placeholders::_2);
        sort(P.begin(),P.end(), mycmp);

        S[0]=P[0]; S[1]=P[1]; top=1;
        for (int i=2; i<nP; i++) {
            while (top && Cross(S[top-1],S[top],S[top],P[i])<=0)
                top--;
            S[++top] = P[i];
        }

    }
    double SqDistance (const mPoint &a, const mPoint &b) {
        return pow(a.x-b.x, 2) + pow(a.y-b.y, 2);
    }
    double MaxDist(vector<vector<int> >& star, double t) {
        int n = star.size();
        for (int i=0; i<n; i++) {
            P[i].x = star[i][0] + t*star[i][2];
            P[i].y = star[i][1] + t*star[i][3];
        }
        FindConvexHull();
        double ret=-1;
        for (int i=0; i<=top; i++) {
            for (int j=i+1; j<=top; j++) {
                ret = max(ret, SqDistance(S[i], S[j]));
            }
        }
        return ret;
    }
    double solve(int n, vector<vector<int> >& star) {
        // write code here

        nP = n;
        P.resize(nP);
        S.resize(nP);
        double ans=1e20;
        double eps=1e-4; 
        double step=1e4, l=0.0, maxd=0;
        while (step>eps) {
            double bestd=1e20, t=l, bestt;
            while(true) {
                maxd = MaxDist(star, t);
                if (maxd<bestd) {
                    bestd = maxd;
                    bestt = t;
                    t+=step;
                }
                else{
                    break;
                }
            }
            l = max(0.0, bestt-step);
            step /= 10.0;
            ans = min(ans, bestd);
        }

        return sqrt(ans);
    }
};