MMRECT2 문제 질문있습니다.

  • Jinsanger
    Jinsanger

    질문하시기 전에

    • 해결하고자 하는 문제가 무엇이며, 어떻게 문제를 해결하려 하였으며, 어떤 어려움을 겪고 있는지 상세히 적어 주세요.

    안녕하세요. 현재 MMRECT2문제를 갖고 쩔쩔매고 있는 초보 개발자입니다. ^^;;
    문제만 읽고서는 쉬운 문제라고 생각하고 풀었는데...
    예제는 잘 나옵니다만 아니나 다를까 제출해보니 RTE가 발생하네요!!! ㅠㅠ

    알고리즘이 워낙 단순해서 시간초과도 아니고, RTE가 뜨리라곤 상상도 못했었는데...

    현재 제 알고리즘은 정말 간단합니다. ;;
    x좌표, y좌표를 각각 오름차순 내림차순으로 배열 시킨 상태에서
    가장 맨 처음 만나는 가로 변의 최대/최소 길이와 세로 변의 최대/최소 길이 차이가 같은 경우에 이 길이를 반환해서 구합니다.

    코드가 어디서 불안정한지 감이 안잡히네요. 다른 테스트 케이스 몇개 돌려봤는데 빠르게 결과도 잘 나오는데 ㅠㅠ

    • 혹시, 크리티컬한 Test case라도 좀 얻을 수 있을까요? ㅜㅠㅠ
    #include <stdio.h>
#include <malloc.h>

static int point[20000][2] = {0, };
static int point_count = 0;

void QuickSortAsc(int* iArray, int left, int right){
    int i=left, j=right;
    int pivot = iArray[(left+right)/2];

    while(i<=j){
        while(iArray[i]<pivot)
            i++;
        while(iArray[j]>pivot)
            j--;
        if(i<=j){
            int temp = iArray[i];
            iArray[i] = iArray[j];
            iArray[j] = temp;
            i++;
            j--;
        }
    }
    if(left<j)
        QuickSortAsc(iArray, left, j);
    if(right>i)
        QuickSortAsc(iArray, i, right);
}
void QuickSortDesc(int* iArray, int left, int right){
    int i=left, j=right;
    int pivot = iArray[(left+right)/2];

    while(i<=j){
        while(iArray[i]>pivot)
            i++;
        while(iArray[j]<pivot)
            j--;
        if(i<=j){
            int temp = iArray[i];
            iArray[i] = iArray[j];
            iArray[j] = temp;
            i++;
            j--;
        }
    }
    if(left<j)
        QuickSortDesc(iArray, left, j);
    if(right>i)
        QuickSortDesc(iArray, i, right);
}
void FuncInit(int N){
    int i=0;
    for(i=0; i<20000; i++){
        point[i][0] = 0;
        point[i][1] = 0;
    }
    point_count = 0;
}
int FuncMax(int index, int N){
    int p_x=0, p_y=0;
    int dist_x=0, dist_y=0;
    int max_dist_x=0, max_dist_y=0, max_dist=-1;
    int i=0, j=0;

    p_x = point[index][0];
    p_y = point[index][1];

    for(i=index+1; i<N; i++){
        dist_x = point[i][0]-p_x;
        dist_y = point[i][1]-p_y;
        if(dist_x<0)    dist_x *= -1;
        if(dist_y<0)    dist_y *= -1;
        if((dist_x>max_dist_x) && (dist_y==0)){
            max_dist_x = dist_x;
        }
        if((dist_y>max_dist_y) && (dist_x==0)){
            max_dist_y = dist_y;
        }
        if(max_dist_x == max_dist_y){
            max_dist = max_dist_x;
            break;
        }
    }
    return max_dist;
}
int FuncMin(int index, int N){
    int p_x=0, p_y=0;
    int dist_x=1000001, dist_y=1000001;
    int min_dist_x=1000001, min_dist_y=1000001, min_dist=1000001;
    int i=0, j=0;

    p_x = point[index][0];
    p_y = point[index][1];

    for(i=index+1; i<N; i++){
        dist_x = point[i][0]-p_x;
        dist_y = point[i][1]-p_x;
        if(dist_x<0)    dist_x *= -1;
        if(dist_y<0)    dist_y *= -1;
        if((dist_x<min_dist_x) && (dist_y==0))
            min_dist_x = dist_x;
        if((dist_y<min_dist_y) && (dist_x==0))
            min_dist_y = dist_y;
        if(min_dist_x == min_dist_y){
            min_dist = min_dist_x;
            break;
        }
    }
    return min_dist;
}
int main(void){
    int T=0, caseCnt=0;
    int resultSet[20][2] = {0, };
    int i=0, j=0;

    scanf("%d", &T);

    while(caseCnt<T){
        int N=0;
        int maxVal=-1, minVal = 1000001;
        int result=0;

        scanf("%d", &N);

        FuncInit(N);

        for(i=0; i<N; i++){
            scanf("%d %d", &point[point_count][0], &point[point_count][1]);
            point_count++;
        }
        QuickSortDesc(&point[point_count][0], 0, N-1);
        QuickSortDesc(&point[point_count][1], 0, N-1);
        for(i=0; i<N; i++){
            int val1 = 0;
            val1 = FuncMax(i, N);
            if(val1 > maxVal)
                maxVal = val1;
        }
        QuickSortAsc(&point[point_count][0], 0, N-1);
        QuickSortAsc(&point[point_count][1], 0, N-1);
        for(i=0; i<N; i++){
            int val2 = 0;
            val2 = FuncMin(i, N);
            if(val2 < minVal)
                minVal = val2;
        }
        resultSet[caseCnt][0] = minVal;
        resultSet[caseCnt][1] = maxVal;
        caseCnt++;
    }
    for(i=0; i<caseCnt; i++)
        printf("%d %d\n", resultSet[i][0], resultSet[i][1]);

    return 0;
}

    앞과 뒤에 빈 줄 하나씩을 반드시 추가하셔야 합니다.


    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    QuickSortDesc()나 QuickSortAsc()를 호출하는 부분에서 첫 번째 인자가 많이 이상한데요? int의 배열도 아니고요.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.