奋战杭电ACM（DAY5）1007

本文主要是介绍奋战杭电ACM（DAY5）1007，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1006题昨天想了整整一天一夜也没有结果……所以跳过了……过会去问一下老师，网上大神的答案都看不懂啊啊啊啊！！

今天搞定了1007，暴力果然是没有好结果的，超时了……

正好前天刚看了递归与分治法，用上了，AC~

不过具体怎么计算算法复杂度还没搞懂，回去再琢磨琢磨！！

Quoit Design

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>using namespace std;#define n 100000
struct point
{double x;double y;
}p1[n],p2[n];bool cpx(point a, point b)
{return a.x<b.x;
}
bool cpy(point a, point b)
{return a.y<b.y;
}double dis(point a,point b)
{return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}double min(double a, double b)
{return a<b ? a : b;
}double mindis(int l,int r)
{if(l+1==r)return dis(p1[l],p1[r]);if(l+2==r)return min(dis(p1[l],p1[l+1]),min(dis(p1[l+1],p1[r]),dis(p1[r],p1[l])));else{double mini;int mid,i,count,j;count=0;mid = (l+r)/2;mini =min(mindis(l,mid), mindis(mid+1,r));for(i=l; i<=r; i++){if(fabs(p1[i].x-p1[mid].x) <=mini){p2[count]=p1[i];	count +=1;}}sort(p2,p2+count,cpy);for(i=0; i<count-1; i++){for(j=i+1; j<count; j++){if(fabs(p2[i].y-p2[j].y) > mini)break;else {if(dis(p2[i],p2[j]) < mini)mini = dis(p2[i],p2[j]);}}}return mini;}
}int main()
{int N;while(cin >> N){if(N==0)break;else{int i;for(i=0; i<N; i++)cin >> p1[i].x >> p1[i].y ;sort(p1,p1+N,cpx);double res;res = mindis(0,N-1);cout << setiosflags(ios::fixed) <<setprecision(2) << res/2 << endl;}}return 0;
}

这篇关于奋战杭电ACM（DAY5）1007的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---