最近点对。不过,数据比较强,需对Y排序。
不断tle,直到重敲一遍代码才A!
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxcost 1e100 #define maxn 100005 class point { public: double x,y; }; point p[maxn]; bool cmp(point a,point b) { if(a.x <b.x ) return true; return false; } int y[maxn]; bool cmpy(int a,int b) { if(p[a].y<p[b].y) return true; return false; } double dist(point a,point b) { return sqrt((a.x-b.x )*(a.x-b.x )+(a.y-b.y )*(a.y-b.y)); } double min_dis(int left,int right) { int i,j; double minlen=maxcost,resultl,resultr; if(right-left>2) { int mid=(left+right)>>1; resultl=min_dis(left,mid); resultr=min_dis(mid+1,right); minlen=resultl<resultr?resultl:resultr; int len=0; for(i=mid;i>=left&&p[i].x+minlen>p[mid].x ;i--) y[++len]=i; for(i=mid+1;i<=right&&p[mid].x +minlen>p[i].x ;i++) y[++len]=i; sort(y+1,y+len+1,cmpy); for(i=1;i<len;i++) for(j=i+1;j<=len;j++) { if(p[y[j]].y -p[y[i]].y>minlen) break; double dis=dist(p[y[j]],p[y[i]]); minlen=dis<minlen?dis:minlen; } } else { double dis; for(i=left;i<right;i++) for(j=i+1;j<=right;j++) { dis=dist(p[i],p[j]); minlen=minlen<dis?minlen:dis; } } return minlen; } int main() { int n,i; while(cin>>n&&n) { for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p,p+n,cmp); double result=min_dis(0,n-1); printf("%.2f\n",result/2); } return 0; }
您还没有登录,请您登录后再发表评论
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj1027解题指南和代码,还不错,是学校培训给的。
zoj吐血制作,希望大家喜欢
ZOJ1805代码
zoj4041正确题解源代码,以及运行程序
zoj 题库 详细解答 解题代码 acm
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
能AC 通过的c++代码,包括zoj1002,1091,1789
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj1027解题指南和代码,还不错,是学校培训给的。
zoj吐血制作,希望大家喜欢
ZOJ1805代码
zoj4041正确题解源代码,以及运行程序
zoj 题库 详细解答 解题代码 acm
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
能AC 通过的c++代码,包括zoj1002,1091,1789
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载