Quoit Design
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 86145 Accepted Submission(s): 23244
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 0.71 0.00 0.75
Author CHEN, Yue
Source ZJCPC2004 题意：给定n个点的坐标，用同样大小的环来套住这些点，每个环必须且仅能套中一个点，求这些环能取到的最大半径是什么。 解析：非常模板的一个平面最近点对，以前一直套模板（因为几何学的不太好），今天终于在https://www.cnblogs.com/duanshuai/p/13163018.html的文章学会了。但是一开始写的找mid两边最近距离的提交一直TLE，因为没有考虑到最坏情况。时间复杂度的对比我已经写在注释里了。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1e5+7;
int n;
struct node {
double x, y;
node(double _x=0, double _y=0):x(_x),y(_y){}
}p[maxn];
int tmp[maxn];
bool cmp(node a, node b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmpy(int a, int b)
{
return p[a].y < p[b].y;
}
double getDis(int a, int b)
{
return sqrt( pow(p[a].x-p[b].x,2) + pow(p[a].y-p[b].y,2) );
}
double stretch(int m, int l, int r, double d)
{/*
int left = m, cnt;
double res = INF;
while(left>=l && p[m].x-p[left].x<= d) left--;
for(int i=left+1; i<=m; i++)
{
cnt = 0;
for(int j=m+1; j<=r; j++)
{
if(p[j].x - p[i].x >= d)break;
if(fabs(p[j].y-p[i].y) < d)
{
res = min(res, getDis(i, j));
cnt ++;
}
if(cnt >= 6) break; //虽然设置了最大6个节点，但是如果y一直不满足条件，最坏的结果是n的，所以这个双重循环了n方了；而先找出所有-d到d的点后排序再找能避免y一直不满足的情况，只做了一个nlogn和n*6的，数量级上优化很多
}
}
return res;*/
int cnt = 0;
double res = INF;
for(int i=l; i<=r; i++)
{
if(p[i].x >= p[m].x-d && p[i].x <= p[m].x+d)
tmp[cnt++] = i;
}
sort(tmp, tmp+cnt, cmpy);
for(int i=0;i<cnt;i++)
{
for(int j=i+1;j<cnt&&j<=i+7;j++)
{
if(p[tmp[j]].y-p[tmp[j]].y >= d) break;
res = min(res, getDis(tmp[i], tmp[j]));
}
}
return res;
}
double findMin(int left, int right)
{
if(left+1 == right)
return getDis(left, right);
else if(left != right)
{
int mid = (left+right) >> 1;
double minLeft = findMin(left, mid);
double minRight = findMin(mid+1, right);
double minMid = stretch(mid, left, right, min(minLeft, minRight));
return min(min(minLeft, minRight), minMid);
}
else return INF;
}
int main()
{
double x, y;
while(~scanf("%d", &n)){
if(!n) break;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf", &x, &y);
p[i].x = x; p[i].y = y;
}
sort(p+1, p+1+n, cmp);
printf("%.2f\n", findMin(1, n)/2);
}
}
标签：HDU,return,int,double,Quoit,Design,res,ring,left From： https://www.cnblogs.com/HazelNut/p/16929929.html