Quoit Design
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 66464 Accepted Submission(s): 17621
Problem Description
Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.
Input
The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.
Output
For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.
Sample Input
2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0
Sample Output
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const double INF = 1e20; const int N = 100005; struct Point { double x; double y; }point[N]; int n; int tmpt_point[N];//For storing the points of |x-m|<=d //Sort the points bool cmpxy(const Point& a, const Point& b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } //Sort the points of y position bool cmpy(const int& a, const int& b) { return point[a].y < point[b].y; } //Comparing the size of two values double min(double a, double b) { return a < b ? a : b; } //Calculate the distance between two points on a plane coordinate (by the algorithm of Euclid) double dis(int i, int j) { return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y)); } //Solving the nearest point problem by divide and conquer method double EfficientClosestPair(int left, int right) { double d = INF; if (left == right) return d; if (left + 1 == right) return dis(left, right); int mid = (left + right) >> 1; double d1 = EfficientClosestPair(left, mid); double d2 = EfficientClosestPair(mid + 1, right); d = min(d1, d2); int i, j, k = 0; for (i = left; i <= right; i++) if (fabs(point[mid].x - point[i].x) <= d) tmpt_point[k++] = i; sort(tmpt_point, tmpt_point + k, cmpy); //Linear sweep for (i = 0; i < k; i++) { for (j = i + 1; j < k&&point[tmpt_point[j]].y - point[tmpt_point[i]].y < d; j++) { double d3 = dis(tmpt_point[i], tmpt_point[j]);//The closest distance may be between two sides if (d>d3) d = d3; } } return d; } int main() { while (true) { scanf("%d", &n);//Input the number of points if (n == 0) break; for (int i = 0; i < n; i++) scanf("%lf %lf", &point[i].x, &point[i].y);//Input the position of points sort(point, point + n, cmpxy);//sort the points printf("%.2lf ", EfficientClosestPair(0, n - 1)/2);//Calculate nearest point pair distance } return 0; }
Homework1
1.Given n points on the plane, design one algorithm to find the distance between the nearest two points with the computational complexity O(nlogn). You should descript this algorithm using pseudocode, and write a program to realize this algorithm.
For example,
Input: n=5
A={(0,2),(6,67),(43,71),(309,107),(189,140)}
Output: 36.22
(1).Algorithm in pseudocode: Algorithm: EfficientClosestPair(P,Q) //Solving the nearest point problem by divide and conquer method //Input: N points on the plane //Output: Euclidean distance between nearest two point pairs if(n<=3) Returns the minimum distance obtained by the brute force method. else: mid←(left+right)/2 Copy the first「n/2」points of P to left(P_left) Copy the first「n/2」points of Q to mid(Q_left) Copy the remaining「n/2」points of P to mid+1(P_right) Copy the remaining「n/2」points of Q to right(Q_right) d1←EfficientClosestPair(left,mid) d2←EfficientClosestPair(mid+1,right) d←min(d1, d2) m←P[「n/2」/2-1].x Copy all |x-m|<=d points of Q to array S[0... k-1] Sort(S) dminsq←d2 for i←0 to k-1 do j←i+1 while(j<=k-1 and (S[j].y-S[i].y)2<d) dminsq←min((S[j].x-S[i].x)2+(S[j].y-S[i].y)2,dminsq) j←j+1 return sqrt(dminsq)
#include<iostream> #include<cstdio> #include <cstring> #include<math.h> #include<algorithm> using namespace std; const double INF = 1e20; const int N = 100005; //之前把两个点之间的距离的变量定义为distance，出现了错误，调了半天才找出来，可能是变量名和内部函数冲突了 //另外，用C语言输入的时候一定要严格按照格式要求，double用lf struct Point { double x; double y; }point[N]; int n; int tempt_point[N]; bool compxy(const Point& a, const Point& b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } bool compy(const int& a, const int& b) { return point[a].y < point[b].y; } double min(double a, double b) { return a < b ? a : b; } double distance_points(int i, int j) { return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y)); } double Close_point(int left, int right) { double d = INF; if (left == right) return d; if (left + 1 == right) return distance_points(left, right); int mid = (left + right) / 2; double d1 = Close_point(left, mid); double d2 = Close_point(mid + 1, right); d = min(d1, d2); int i, j, k = 0; for (i = left; i <= right;i++) if (fabs(point[mid].x - point[i].x) < d) tempt_point[k++] = i; sort(tempt_point, tempt_point + k, compy); for (i = 0; i < k; i++) { for (j = i+1; j < k&&point[tempt_point[j]].y - point[tempt_point[i]].y < d;j++) { double d3 = distance_points(tempt_point[i], tempt_point[j]); if (d3 < d) d = d3; } } return d; } int main() { while (1) { cin >> n; if (n == 0) break; int i, k; for (i = 0; i < n; i++) scanf("%lf%lf", &point[i].x ,&point[i].y); sort(point, point + n , compxy); printf("%.2lf ",Close_point(0, n-1)/2); } return 0; }