面试官准时到，总共面试时间一小时二十分钟，一面主要问基础知识

C++

1. vector resize和reserve区别
2. 返回值优化
3. 缓存命中率
4. map 和 unordered map区别，空间很多时间很紧，选择哪一个
5. map里面[]和at有什么区别

1. aMap是map类的对象，通过aMap[key]取值和通过aMap.at(key)取值的区别如下：

aMap[key]如果key不存在会添加key，不会抛出异常；

1. 如果在vector中写一个第k小的元素，find_kth函数，该怎么构建？

1. 和快排思路很像，快排是怎么实现的？

1. 随机取一个值，然后左右指针遍历，比这个值大的放右边

1. find_kth思路和快排很相似：
2. 这种方法时间复杂度是多少？

1. O(2n)

多视图题目

1. 对级线和对级点是什么关系？对级约束具体的物理意义是什么？
2. 如果相机是平移运动，那么对级线是什么样子？

视觉算法题

1. 给出一个三角形的三个点的坐标，该三个点构建一个三角形，写一个函数，可以输出三角形内随机的一个点的位置。

代码题

bool Intersect(double x_bl, double y_bl, double x_tr, double y_tr, double xc, double yc, double r) {
    // 获得矩形描述
    double width = x_tr - x_bl;
    double height = y_tr - y_bl;
    double rect_mid_x = x_bl + width / 2;
    double rect_mid_y = y_bl + height / 2;

    // change circle center to First region

    double new_xc, new_yc;
    // 2 region
    if(xc > rect_mid_x && yc < rect_mid_y){
        new_xc = xc;
        new_yc = yc + (rect_mid_y - yc) * 2;
    } 
    else if (xc < rect_mid_x && yc < rect_mid_y){
        new_xc = xc + (rect_mid_x - xc) * 2;
        new_yc = yc + (rect_mid_y - yc) * 2;
    }
    else if (xc < rect_mid_x && yc > rect_mid_y) {
        new_xc = xc + (rect_mid_x - xc) * 2;
        new_yc = yc;
    }
    else {
        new_xc = xc;
        new_yc = yc;
    }
    
    // get distance;
    double u = GetNearestDistance(x_tr - rect_mid_x, y_tr - rect_mid_y,
                                  new_xc- rect_mid_x, new_yc - rect_mid_y);

    if(u < r)
        return true;
    
    return false;
    
}

double GetNearestDistance(double x, double y, double x_p, double y_p) {
    double dx = x_p - x;
    double dy = y_p - y;   

    double distance = sqrt(pow(max(dx, 0), 2) + pow(max(dy, 0)));
    return distance;
}

https://www.zhihu.com/question/24251545/answer/27184960