Careercup - Google面试题 - 4877486110277632

2014-05-08 05:16

原题：

Given a circle with N defined points and a point M outside the circle, find the point that is closest to M among the set of N. O(LogN)

题目：给定一个圆上的N个点，和一个在这个圆外部的点。请找出这N个点中与外部点最近的那个。要求时间复杂度是对数级的。

解法1：这位“Guy”老兄又出了一道莫名奇妙的题：1. 这些点是等距离的吗？2. 这些点是顺时针还是逆时针排列的？在没有比较清楚思路的情况下，我只写了个O(n)枚举的算法。

代码：

 // http://www.careercup.com/question?id=4877486110277632

 #include <cmath>

 #include <iostream>

 #include <vector>

 using namespace std;

 struct Point {

     double x;

     double y;

     Point(double _x = , double _y = ): x(_x), y(_y) {};

 };

 double dist(const Point &p1, const Point &p2)

 {

     return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));

 }

 int main()

 {

     int i, n;

     Point pout;

     vector<Point> vp;

     int min_i;

     double d, min_d;

     while (cin >> n && n > ) {

         vp.resize(n);

         for (i = ; i < n; ++i) {

             cin >> vp[i].x >> vp[i].y;

         }

         cin >> pout.x >> pout.y;

         min_i = ;

         min_d = dist(pout, vp[]);

         for (i = ; i < n; ++i) {

             d = dist(pout, vp[i]);

             min_i = d < min_d ? i : min_i;

         }

         cout << '(' << vp[min_i].x << ',' << vp[min_i].y << ')' << endl;

         cout << min_d << endl;

         vp.clear();

     }

     return ;

 }

解法2：实际上这题不但有对数级算法，还有常数级算法。但有一个额外条件需要满足：我得知道圆心在哪儿。计算圆心需要把所有点的坐标求平均值，那样的算法复杂度还是线性的。如果我们定义P[i]为圆上的那N个点，O为圆心，M为圆外的那个点。那么我们连接OP[i]与OM，可以发现OM与OP[i]的夹角分布是循环有序的(参见Leetcode里面的Rotated Sorted Array)，条件是这N个点呈顺时针或逆时针分布。你可以通过二分得到距离最小的结果，但更快的算法是常数级的。你只要计算一个夹角，就知道所有的了。因为这些夹角是个等差数列。比如四个点中，有一个的夹角是73°，那么另外三个肯定是163°、107°(253°)、17°(343°)。谁的距离最短呢？角度最小的就是了，注意优角要换算成锐角或钝角。想要通过一次计算就解决问题，用除法和取模的思想吧。此处的代码默认点是按照顺时针排列的，否则为了判断哪个方向，又得进行一些计算。那样的话，代码都乱的看不清楚了。

代码：

 // http://www.careercup.com/question?id=4877486110277632

 #include <cmath>

 #include <iostream>

 #include <vector>

 using namespace std;

 struct Point {

     double x;

     double y;

     Point(double _x = , double _y = ): x(_x), y(_y) {};

     Point operator - (const Point &other) {

         return Point(x - other.x, y - other.y);

     };

     Point operator + (const Point &other) {

         return Point(x + other.x, y + other.y);

     };

     double operator * (const Point &other) {

         return x * other.x + y * other.y;

     };

 };

 double dist(const Point &p1, const Point &p2)

 {

     return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));

 }

 int main()

 {

     int i, n;

     Point pout;

     vector<Point> vp;

     Point center;

     Point v0, vout;

     // the angle between OM and a line of center

     double angle;

     // 2 * pi / n

     double side_angle;

     const double pi = 3.1415926;

     double d;

     while (cin >> n && n > ) {

         vp.resize(n);

         for (i = ; i < n; ++i) {

             cin >> vp[i].x >> vp[i].y;

         }

         cin >> center.x >> center.y;

         cin >> pout.x >> pout.y;

         v0 = vp[] - center;

         vout = pout - center;

         side_angle =  * pi / n;

         angle = arccos((v0 * vout) / (dist(vp[], center) * dist(pout, center)));

         d = angle / side_angle;

         // Here I assume the points are arranged in clockwise order.

         i = d - floor(d) < 0.5 ? floor(d) : floor(d) + ;

         cout << vp[i].x << ' ' << vp[i].y << endl;

         vp.clear();

     }

     return ;

 }

巴特西

Careercup - Google面试题 - 4877486110277632

最新文章

热门文章