William_Prince 发表于 2021-10-31 01:11:03

C语言 最近对问题

下面是题目和测试用例


以下是我的代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define INF 2147483647
#define N 1000000

struct node{
        int x;
        int y;
}point;

int cmp(const void *a,const void *b)
{
        struct node ac = *(struct node*)a;
        struct node bd = *(struct node*)b;
        if (ac.x != bd.x)
                return ac.x - bd.x;
        else return ac.y - bd.y;
}//结构体排序


int mindistance(int left,int right){
        return left<right?left:right;//返回大小关系
}

int distance(int left,int right){
        return ((point.x - point.x)*(point.x - point.x) + (point.y - point.y)*(point.y - point.y));
}//计算距离的平方

int Closest_Pair(int left,int right){
        int End_dis = INF;
        int i=0,j=0,k=0;
       
        if (left == right) return End_dis;//假如区间里面只有一个点，那么返回无穷大
        if (right - left == 1) return distance(left,right);//假如区间里面只有两个点，那么直接返回这两点之间距离的平方
       
       
        int mid = (left + right)/2;//计算中线，判断是否是大于等于三个点的情况
       
        int distanceleft= Closest_Pair(left,mid);//左边递归
        int distanceright = Closest_Pair(mid+1,right);//右边递归
       
        End_dis = mindistance(distanceleft,distanceright) ;//比较左右两边距离的平方，找出最小值，即为d
       
        int temp = {0}; //储存宽度为d的点
       
        for (i = left; i < right; i++){//找出符合要求的距离mid横坐标的平方小于d的点
                if ( (point.x - point.x)*(point.x - point.x) <= End_dis ){
                        temp = i;//temp用来暂时存储符合要求的点的序号
                }
        }
        for (i=0; i<k; i++){
                for(j=i+1; j<k&&j<i+7; j++){
                        if ((point].y - point].y)*(point].y - point].y) <End_dis)
                                End_dis = mindistance(End_dis,distance(temp,temp));
                }
        }
        return End_dis;       
}

int main(){
        int n,i;
        scanf("%d",&n);
        for(i=0;i<n;i++){
                scanf ("%d %d",&point.x,&point.y);
        }
        qsort(point,n,sizeof(point),cmp);
        printf("%d\n",Closest_Pair(0,n-1));
        return 0;
}
这个代码第一个测试用例就过不去，我想请问一下问题出在哪里
同时，假如我把数组开到10^6，不管我输入什么，都会出现下图问题

想请教一下大家问题出在哪里，谢谢！

jhq999 发表于 2021-10-31 01:11:04


静态数组定义的太大了。
int Closest_Pair(int left,int right){
      int End_dis = INF;
      int i=0,j=0,k=0;
      
      if (left == right) return End_dis;//假如区间里面只有一个点，那么返回无穷大
      if (right - left == 1) return distance(left,right);//假如区间里面只有两个点，那么直接返回这两点之间距离的平方
         
      
      int mid = (left + right)/2;//计算中线，判断是否是大于等于三个点的情况
      
      int distanceleft= Closest_Pair(left,mid);//左边递归
      int distanceright = Closest_Pair(mid+1,right);//右边递归
      
      End_dis = mindistance(distanceleft,distanceright) ;//比较左右两边距离的平方，找出最小值，即为d
      //////////
      int *temp = new int; //储存宽度为d的点
      //////////
      for (i = left; i < right; i++){//找出符合要求的距离mid横坐标的平方小于d的点
                if ( (point.x - point.x)*(point.x - point.x) <= End_dis ){
                        temp = i;//temp用来暂时存储符合要求的点的序号
                }
      }
      for (i=0; i<k; i++){
                for(j=i+1; j<k&&j<i+7; j++){
                        if ((point].y - point].y)*(point].y - point].y) <End_dis)
                              End_dis = mindistance(End_dis,distance(temp,temp));
                }
      }
                delete[] temp;////////////
      return End_dis;      
}

傻眼貓咪 发表于 2021-10-31 08:12:14

n 不超过 1000000
x、y不超过 10000
以你的代码时间复杂度，不超时（TLE）吗？

William_Prince 发表于 2021-10-31 19:40:13

jhq999 发表于 2021-10-31 01:11
静态数组定义的太大了。

谢谢！这段改完之后还是有一个超时，然后我把数组开到全局变量里头就过了。
页: [1]
查看完整版本: C语言 最近对问题