首页 > 代码库 > hdu 刷题记录
hdu 刷题记录
1007 最近点对问题,采用分治法策略搞定
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int n; 6 struct node 7 { 8 double x; 9 double y;10 }p[100005];11 int a[100005];12 double cmpx(node a,node b)13 {14 return a.x<b.x;15 }16 double cmpy(int a,int b)17 {18 return p[a].y<p[b].y;19 }20 double min(double a,double b)21 {22 return a<b?a:b;23 }24 double dis(node a,node b)25 {26 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));27 }28 double find(int l,int r)29 {30 if(r==l+1)31 return dis(p[l],p[r]);32 if(l+2==r)33 return min(dis(p[l],p[r]),min(dis(p[l],p[l+1]),dis(p[l+1],p[r])));34 int mid=(l+r)>>1;35 double ans=min(find(l,mid),find(mid+1,r));36 int i,j,cnt=0;37 for(i=l;i<=r;i++)38 {39 if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans)40 a[cnt++]=i;41 }42 sort(a,a+cnt,cmpy);43 for(i=0;i<cnt;i++)44 {45 for(j=i+1;j<cnt;j++)46 {47 if(p[a[j]].y-p[a[i]].y>=ans) break;48 ans=min(ans,dis(p[a[i]],p[a[j]]));49 }50 } 51 return ans;52 }53 int main()54 {55 int i;56 57 while(scanf("%d",&n)!=EOF)58 {59 if(!n) break;60 for(i=0;i<n;i++)61 scanf("%lf %lf",&p[i].x,&p[i].y);62 sort(p,p+n,cmpx);63 printf("%.2lf%\n",find(0,n-1)/2);64 }65 return 0;66 }
1008 沙茶题,水题预警
1 #include<stdio.h> 2 int main() 3 { 4 int n; 5 int start,a; 6 int t; 7 int i; 8 while(scanf("%d",&n),n) 9 {10 t=0;start=0;11 for(int i=1;i<=n;i++)12 {13 scanf("%d",&a);14 if(a>start)t+=6*(a-start);15 else t+=4*(start-a);16 t+=5;17 start=a;18 }19 printf("%d\n",t);20 } 21 return 0; 22 }
hdu 刷题记录
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。