注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu]1007 Quoit Design  

2012-08-03 13:15:49|  分类: HDU |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近新生进来在忙着招待新生,再加上在倒腾域名,也就好几天木有切题了。、
不过一阵子不切是有点难过,真的生病了吗...
说题目吧,这题的意思就是给你N个点,求出两个点之间对短的距离,再除以2.
看的题目我们就知道可以套模板了,平面最近点对的模板。
先放上题目:

Quoit Design


Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15358    Accepted Submission(s): 3819


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
 

Recommend
JGShining
 

代码如下:


#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 100005;
const double MAX = 10e100, eps = 0.00001;
struct Point { double x, y; int index; };
Point a[N], b[N], c[N];

double closest(Point *, Point *, Point *, int, int);
double dis(Point, Point);
int cmp_x(const void *, const void*);
int cmp_y(const void *, const void*);
int merge(Point *, Point *, int, int, int);
inline double min(double, double);

int main()
{
int n, i;
double d;
scanf("%d", &n);
while (n)
{
for (i = 0; i < n; i++)
scanf("%lf%lf", &(a[i].x), &(a[i].y));
qsort(a, n, sizeof(a[0]), cmp_x);
for (i = 0; i < n; i++)
a[i].index = i;
memcpy(b, a, n *sizeof(a[0]));
qsort(b, n, sizeof(b[0]), cmp_y);
d = closest(a, b, c, 0, n - 1);
printf("%.2lf\n", d/2);
scanf("%d", &n);
}
return 0;
}
double closest(Point a[],Point b[],Point c[],int p,int q){
if (q - p == 1) return dis(a[p], a[q]);
if (q - p == 2) {
double x1 = dis(a[p], a[q]);
double x2 = dis(a[p + 1], a[q]);
double x3 = dis(a[p], a[p + 1]);
if (x1 < x2 && x1 < x3) return x1;
else if (x2 < x3) return x2;
else return x3;
}
int i, j, k, m = (p + q) / 2;
double d1, d2;
for (i = p, j = p, k = m + 1; i <= q; i++)
if (b[i].index <= m) c[j++] = b[i];
//数组c左半部保存划分后左部的点, 且对y是有序的.
else c[k++] = b[i];
d1 = closest(a, c, b, p, m);
d2 = closest(a, c, b, m + 1, q);
double dm = min(d1, d2);
//数组c左右部分分别是对y坐标有序的, 将其合并到b.
merge(b, c, p, m, q);
for (i = p, k = p; i <= q; i++)
if (fabs(b[i].x - b[m].x) < dm) c[k++] = b[i];
//找出离划分基准左右不超过dm的部分, 且仍然对y坐标有序.
for (i = p; i < k; i++)
for (j = i + 1; j < k && c[j].y - c[i].y < dm; j++){
double temp = dis(c[i], c[j]);
if (temp < dm) dm = temp;
}
return dm;
}
double dis(Point p, Point q){
double x1 = p.x - q.x, y1 = p.y - q.y;
return sqrt(x1 *x1 + y1 * y1);
}
int merge(Point p[], Point q[], int s, int m, int t){
int i, j, k;
for (i=s, j=m+1, k = s; i <= m && j <= t;) {
if (q[i].y > q[j].y) p[k++] = q[j], j++;
else p[k++] = q[i], i++;
}
while (i <= m) p[k++] = q[i++];
while (j <= t) p[k++] = q[j++];
memcpy(q + s, p + s, (t - s + 1) *sizeof(p[0]));
return 0;
}
int cmp_x(const void *p, const void *q){
double temp = ((Point*)p)->x - ((Point*)q)->x;
if (temp > 0) return 1;
else if (fabs(temp) < eps) return 0;
else return - 1;
}
int cmp_y(const void *p, const void *q){
double temp = ((Point*)p)->y - ((Point*)q)->y;
if (temp > 0) return 1;
else if (fabs(temp) < eps) return 0;
else return - 1;
}
inline double min(double p, double q)
{
return (p > q) ? (q): (p);
}
/*
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
*/


想进一步了解最近点对的~推荐一个博客 http://www.cnblogs.com/blong880123/archive/2012/04/16/2451244.html
很详细~
  评论这张
 
阅读(368)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018