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 #include3 #include 4 #include 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 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 #include3 #include 4 #include 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 vp;35 Point center;36 Point v0, vout;37 // the angle between OM and a line of center38 double angle;39 // 2 * pi / n40 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 }