读书人

杭电acm1173有关问题求解

发布时间: 2012-06-04 14:48:03 作者: rapoo

杭电acm1173问题求解啊
#include <stdio.h>
double a[1000001];
double b[1000001];
int main()
{
int n,i,j;
double t;
while(scanf("%d",&n)!=EOF)
{
if(0==n)break;
for(i=0;i<n;i++)
scanf("%lf%lf",&a[i],&b[i]);
for(i=0;i<n-1;i++)
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
if(b[j]>b[j+1])
{t=b[j];b[j]=b[j+1];b[j+1]=t;}
}
if(n%2==0)printf("%.2lf %.2lf\n",(a[n/2]+a[n/2-1])/2.0,(b[n/2]+b[n/2-1])/2.0);
else printf("%.2lf %.2lf\n",a[n/2],b[n/2]);
}
return 0;
}

//不知道哪出问题啦?题目网站http://acm.hdu.edu.cn/showproblem.php?pid=1173

[解决办法]
你的算法是错误的。你认为简单的排序就能求得到所有点的最短距离了么???
[解决办法]
楼主,你这样算法是对的,只是这个题目用 冒泡超时(TLE),用快排吧:

C/C++ code
#include <stdio.h>#include <stdlib.h>double a[1000001];double b[1000001];int cmp( const void *a,const void *b )  {          return *( ( double * )a ) > *( ( double * )b ) ? 1 : -1;      }  int main(){    int n,i,j;    double t;    while(scanf("%d",&n)!=EOF)    {        if(0==n)break;        for(i=0;i<n;i++)            scanf("%lf%lf",&a[i],&b[i]);    /*    for(i=0;i<n-1;i++)            for(j=0;j<n-1-i;j++)            {                if(a[j]>a[j+1])                {                    t=a[j];a[j]=a[j+1];a[j+1]=t;                }                if(b[j]>b[j+1])                {                    t=b[j];b[j]=b[j+1];b[j+1]=t;                }            }            */        qsort(a, n, sizeof(a[0]),cmp);        qsort(b, n, sizeof(b[0]),cmp);        if(n%2==0)printf("%.2lf %.2lf\n",(a[n/2]+a[n/2-1])/2.0,(b[n/2]+b[n/2-1])/2.0);        else printf("%.2lf %.2lf\n",a[n/2],b[n/2]);    }    return 0;} 

读书人网 >C语言

热点推荐