求平面最近点对
对于平面上N个点，求其中两个距离最近的点。输入格式：点的个数N，然后是N个坐标即可计算出。
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdlib.h>
struct pos {double x, y;};
typedef struct pos Pos;
Pos p[100000];
int d[100000];
double eps = 0.00001;
int cmp_x(const void *p, const void *q)
{
double tmp=((Pos*)p)->x-((Pos*)q)->x;
if(tmp>0) return 1;
else if(fabs(tmp)<eps) return 0;
else return -1;
}
double Dest(Pos p2, Pos p1)
{
return ((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
double Min(double a, double b)
{
return a < b ? a : b;
}
int cmp(const void *a, const void *b)
{
return(*(int *)a-*(int *)b);
}
double NSP(int left, int right)
{
double m1, m2, m3 , res;
int i, j, ix, mid;
if(right - left == 1)
return Dest(p[right], p[left]);
else if(right - left == 2)
{
m1 = Dest(p[left], p[left+1]);
m2 = Dest(p[left], p[left+2]);
m3 = Dest(p[left+1], p[left+2]);
return Min(m1, Min(m2, m3));
}
mid = (left+right)/2;
res = Min(NSP(left, mid), NSP(mid+1, right));
ix = 0;
for(i = mid; i>=left && p[mid].x-p[i].x < res; --i)
d[ix++] = i;
for(i = mid+1; i<=right && p[i].x-p[mid+1].x < res; ++i)
d[ix++] = i;
qsort(d, ix, sizeof(d[0]), cmp);
for(i = 0; i < ix; ++i)
for(j = i+1; j<ix && j<i+4 && p[d[j]].y-p[d[i]].y < res; ++j)
res = Min(res, Dest(p[d[j]], p[d[i]]));
return res;
}
int main(void)
{
int N, i;
while(scanf("%d", &N), N)
{
assert(N!=1 && N<100000);
for(i = 0; i < N; ++i)
scanf("%lf %lf", &p[i].x, &p[i].y);
qsort(p, N, sizeof(p[0]), cmp_x);
printf("%.2lf\n", sqrt(NSP(0, N-1)));
}
return 0;
}
用的是分治法。
2020年4月22日 03:32
Usually while I surf the 'net I look for web-sites which provide reliable information and so I found this site. Pleased when I came across your web blog because I greatly liked this and that I look forward to your next post. An incredible web-site and i'll come back again for further useful content… us phone number redirect
2020年4月25日 21:41
For this web site, you will see our account, remember to go through this info. buy phenq
2020年5月07日 17:09
There is so much in this article that I would never have thought of on my own. Your content gives readers things to think about in an interesting way.https://www.thelostwaysreview.eubookshop.com/the-lost-book-of-remedies-review/
2020年5月07日 18:29
Amazing, this is great as you want to learn more, I invite to This is my page. his secret obsession
2020年5月13日 05:55
Acknowledges for penmanship such a worthy column, I stumbled beside your blog besides predict a handful advise. I want your tone of manuscript... Arya Toufanian
2020年5月14日 23:13
Thanks for writing such a good article, I stumbled onto your blog and read a few post. I like your style of writing... Benefits of Rutabagas
2020年5月15日 08:05
Your blogs further more each else volume is so entertaining further serviceable It appoints me befall retreat encore. I will instantly grab your rss feed to stay informed of any updates.Essential Oils for Wrinkles
2020年5月15日 08:10
It is somewhat fantastic, and yet check out the advice at this treat. Foods That Helps Boost Your Mood
2020年5月15日 08:14
During this website, you will see this shape, i highly recommend you learn this review. Benefits Of Pomegranates
2020年5月15日 08:19
Cool you write, the information is very good and interesting, I'll give you a link to my site. Benefits of Orach
2020年5月15日 08:23
I invite you to the page where see how much we have in common. Benefits of Lemongrass Essential Oil
2020年5月15日 08:28
You possess lifted an essential offspring..Blesss for using..I would want to study better latest transactions from this blog..preserve posting.. Benefits of Garlic
2020年5月22日 18:08
Such a very useful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. новини
2020年5月22日 18:16
It has fully emerged to crown Singapore's southern shores and undoubtedly placed her on the global map of residential landmarks. I still scored the more points than I ever have in a season for GS. I think you would be hard pressed to find somebody with the same consistency I have had over the years so I am happy with that. хотели гърция
2020年5月22日 18:22
Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I’ll be subscribing to your feed and I hope you post again soon.работни обувки
2020年5月22日 18:27
This post is very simple to read and appreciate without leaving any details out. Great work! мебели варна
2020年5月22日 18:36
I can give you the address Here you will learn how to do it correctly. Read and write something good. принтери варна
2020年5月22日 18:40
I should assert barely that its astounding! The blog is informational also always fabricate amazing entitys. тениски
2020年5月27日 14:03
You bear through a awesome vacancy. I sanity definitely quarry it moreover personally suggest to my buddys. I am self-possessed they determination be benefited from this scene.Insta Followers Pro
2020年6月01日 03:12
You should mainly superior together with well-performing material, which means that see it: a course in miracles unity online radio
2020年6月01日 03:30
On my website you'll see similar texts, write what you think. acim david hoffmeister audio
2020年6月01日 03:35
I read this article. I think You put a lot of effort to create this article. I appreciate your work. spotify david hoffmeister
2020年6月04日 18:23
It's superior, however , check out material at the street address. mondaymotivation
2020年6月08日 22:03
This is very interesting, but it is necessary to click on this link: voyance retour amour
2020年6月12日 20:37
In this case you will begin it is important, it again produces a web site a strong significant internet site: essential oils for back pain
2020年6月18日 13:52
I can give you the address Here you will learn how to do it correctly. Read and write something good.https://www.butywolka.eu/
2020年6月20日 03:18
In this particular article, you will see a summary, satisfy browse this post. Marketing agency Sydney
2020年6月20日 14:25
Actually I read it yesterday but I had some thoughts about it and today I wanted to read it again because it is very well written. Coloradocreditrepair
2020年6月26日 19:41
I like to recommend exclusively fine plus efficient information and facts, hence notice it: Agenzia SEO
2020年6月28日 15:54
I invite you to the page where see how much we have in common. A4 Display Stand
2020年7月02日 18:59
I prefer merely excellent resources - you will see these people in: www.iphysio.sg
2020年7月02日 19:12
During this website, you will see this shape, i highly recommend you learn this review. https://www.dynamicmarketing.sg
2020年7月04日 19:00
그리고 샴페인 콜,(손님이 특정 금액 이상의 샴페인을 시켰을 때 진행되며 대체로 6만엔에서 8만엔 정도일때 들어간다.) 혹은 술을 원샷 할 시에 사용 할 수 있는 방법이 있다. 보통의 호스트바에서는 술을 원샷 할 때 다른 호스트가 물수건을 입가에 받쳐준다. 이는 마시는 동안 술이 흘러 옷이라던가 가게가 더럽혀지지 않게 하기위한 행위인데, 바로 이 때 술을 전부 마시지않고 적당량 물수건에 흡수시켜 버리는 것 이다. 애초에 술의 양에 따라 모든 술을 물수건에 흡수시키기는 어렵기 때문에 주의와 컨트롤 능력이 필요하다. 호빠
2020年7月09日 14:02
해외사이트 해외토토 추천 토토사이트 안전놀이터 업계최고 퀸88벳 해외사이트
2020年7月17日 12:36
On my website you'll see similar texts, write what you think. Military Miniatures
2020年7月19日 19:45
Such sites are important because they provide a large dose of useful information ... Buy Instagram Followers
2020年7月24日 19:06
There is so much in this article that I would never have thought of on my own. Your content gives readers things to think about in an interesting way. ICON
2020年7月27日 23:07
Gangaur Realtech is a professionally managed organisation specializing in real estate services where integrated services are provided by professionals to its clients seeking increased value by owning, occupying or investing in real estate. copripiumino matrimoniale
2020年7月28日 02:51
For true fans of this thread I will address is a free online!Pamela Obame Watara
2020年7月30日 20:02
Thanks for writing such a good article, I stumbled onto your blog and read a few post. I like your style of writing... www.matures-webcam.com
2020年8月03日 01:21
So it is interesting and very good written and see what they think about other people. bitcoin casinos
2022年10月03日 13:44
You can use Bank Passbook, Account Statement, Visit the Home Branch and Call the Customer Care to Find Your City Union Bank Customer ID. The customers receive User ID and Password for net banking. The User ID or enquiry number Check City Union Bank Account Balance Through Missed Call. cub customer id check The customers receive User ID and Password for net banking. The User ID or enquiry number Check City Union Bank Account Balance Through Missed Call.The customers receive User ID and Password for net banking. The User ID or enquiry number Check City Union Bank Account Balance Through Missed Call.
2023年2月15日 16:20
Class 11th Question Paper 2024 Every one of the students are right now sitting tight for the 11th test Model Paper to be Download, so need to reveal to you that as per the data got from the sources as of late, +1 Model Paper 2024 The board will deliver its 11th test Model Paper, realizing that it will be made accessible to you. So continue to check this post consistently.
2023年4月23日 19:32
crediblebh