首页 > 代码库 > 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 }
View Code

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 }
View Code

 

hdu 刷题记录