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)枚舉的算法。

代碼：

1 // http://www.careercup.com/question?id=4877486110277632 2 #include <cmath> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 struct Point { 8 double x; 9 double y; 10 Point(double _x = 0, double _y = 0): x(_x), y(_y) {}; 11 }; 12 13 double dist(const Point &p1, const Point &p2) 14 { 15 return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); 16 } 17 18 int main() 19 { 20 int i, n; 21 Point pout; 22 vector<Point> vp; 23 int min_i; 24 double d, min_d; 25 26 while (cin >> n && n > 0) { 27 vp.resize(n); 28 for (i = 0; i < n; ++i) { 29 cin >> vp[i].x >> vp[i].y; 30 } 31 cin >> pout.x >> pout.y; 32 33 min_i = 0; 34 min_d = dist(pout, vp[0]); 35 for (i = 1; i < n; ++i) { 36 d = dist(pout, vp[i]); 37 min_i = d < min_d ? i : min_i; 38 } 39 cout << '(' << vp[min_i].x << ',' << vp[min_i].y << ')' << endl; 40 cout << min_d << endl; 41 vp.clear(); 42 } 43 44 return 0; 45 }

?解法2：實際上這題不但有對數級算法，還有常數級算法。但有一個額外條件需要滿足：我得知道圓心在哪兒。計算圓心需要把所有點的坐標求平均值，那樣的算法復雜度還是線性的。如果我們定義P[i]為圓上的那N個點，O為圓心，M為圓外的那個點。那么我們連接OP[i]與OM，可以發現OM與OP[i]的夾角分布是循環有序的(參見Leetcode里面的Rotated Sorted Array)，條件是這N個點呈順時針或逆時針分布。你可以通過二分得到距離最小的結果，但更快的算法是常數級的。你只要計算一個夾角，就知道所有的了。因為這些夾角是個等差數列。比如四個點中，有一個的夾角是73°，那么另外三個肯定是163°、107°(253°)、17°(343°)。誰的距離最短呢？角度最小的就是了，注意優角要換算成銳角或鈍角。想要通過一次計算就解決問題，用除法和取模的思想吧。此處的代碼默認點是按照順時針排列的，否則為了判斷哪個方向，又得進行一些計算。那樣的話，代碼都亂的看不清楚了。

代碼：

1 // http://www.careercup.com/question?id=4877486110277632 2 #include <cmath> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 struct Point { 8 double x; 9 double y; 10 Point(double _x = 0, double _y = 0): x(_x), y(_y) {}; 11 12 Point operator - (const Point &other) { 13 return Point(x - other.x, y - other.y); 14 }; 15 16 Point operator + (const Point &other) { 17 return Point(x + other.x, y + other.y); 18 }; 19 20 double operator * (const Point &other) { 21 return x * other.x + y * other.y; 22 }; 23 }; 24 25 double dist(const Point &p1, const Point &p2) 26 { 27 return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); 28 } 29 30 int main() 31 { 32 int i, n; 33 Point pout; 34 vector<Point> vp; 35 Point center; 36 Point v0, vout; 37 // the angle between OM and a line of center 38 double angle; 39 // 2 * pi / n 40 double side_angle; 41 const double pi = 3.1415926; 42 double d; 43 44 while (cin >> n && n > 0) { 45 vp.resize(n); 46 for (i = 0; i < n; ++i) { 47 cin >> vp[i].x >> vp[i].y; 48 49 } 50 cin >> center.x >> center.y; 51 cin >> pout.x >> pout.y; 52 53 v0 = vp[0] - center; 54 vout = pout - center; 55 56 side_angle = 2 * pi / n; 57 angle = arccos((v0 * vout) / (dist(vp[0], center) * dist(pout, center))); 58 d = angle / side_angle; 59 // Here I assume the points are arranged in clockwise order. 60 i = d - floor(d) < 0.5 ? floor(d) : floor(d) + 1; 61 cout << vp[i].x << ' ' << vp[i].y << endl; 62 63 vp.clear(); 64 } 65 66 return 0; 67 }

?

轉載于:https://www.cnblogs.com/zhuli19901106/p/3715309.html

總結

以上是生活随笔為你收集整理的Careercup - Google面试题 - 4877486110277632的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。