글 읽기 - 80% 틀립니다 ㅠㅠㅠ 어떤 케이스가 미스인걸까요..

changco 6년 전 0

sort 부분은 괜찮은데 Closest Pair 부분이 문제인 것 같은데 도저히 모르겠네요 ㅠㅠ
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct dot {
	int id ;
	int x;
	int y ;
}dot;
typedef struct pair {
	dot a;
	dot b;
	int dis;
}pair;

void Merge(dot *A, int p, int k, int q, int tri) {

	int i = p;
	int j = k + 1;
	int d = p;
	int temp1 = 0;
	int index;
	dot*U = (dot*)malloc((q + 1) * sizeof(dot));
	if (tri == 0) {

		while (i <= k && j <= q) {
			if (A[i].x < A[j].x) {
				U[d] = A[i];
				i++;
			}
			else {
				U[d] = A[j];
				j++;
			}
			d++;
		}
		if (i > k) {

			int temp1 = j, temp2 = d;
			for (; temp1 <= q; ) {
				U[temp2] = A[temp1];
				temp1++;
				temp2++;
			}
		}
		else {
			int temp1 = i, temp2 = d;
			for (; temp1 <= k; ) {
				U[temp2] = A[temp1];
				temp1++;
				temp2++;
			}
		}
		for (temp1 = p; temp1 <= q; temp1++) {
			A[temp1] = U[temp1];
		}
	}
	else {
		while (i <= k && j <= q) {
			if (A[i].y < A[j].y) {
				U[d] = A[i];
				i++;
			}
			else {
				U[d] = A[j];
				j++;
			}
			d++;
		}
		if (i > k) {

			int temp1 = j, temp2 = d;
			for (; temp1 <= q; ) {
				U[temp2] = A[temp1];
				temp1++;
				temp2++;
			}
		}
		else {
			int temp1 = i, temp2 = d;
			for (; temp1 <= k; ) {
				U[temp2] = A[temp1];
				temp1++;
				temp2++;
			}
		}
		for (temp1 = p; temp1 <= q; temp1++) {
			A[temp1] = U[temp1];
		}
	}
	free(U);
}

void Sort_by_X_or_Y(dot* A, int p, int q, int tri) {
	int k;
	if (p < q) {
		k = (p + q) / 2;
		Sort_by_X_or_Y(A, p, k, tri);
		Sort_by_X_or_Y(A, k + 1, q, tri);
		Merge(A, p, k, q, tri);
	}


}
int dist(dot a, dot b) {

	int dist;
	dist = pow((a.x - b.x), 2) + pow((a.y - b.y), 2);
	return dist;
}

pair Closest_Pair_DC(dot* DOT, int n) {


	pair closest_pair;
	pair right_pair;
	pair left_pair;
    int index1,index2;


	int temp_num;
	int right_num;
	int left_num;
	
    
    if(n==2) {
        closest_pair.a=DOT[0];
        closest_pair.b=DOT[1];
        closest_pair.dis=dist(DOT[0],DOT[1]);
        return closest_pair;
    }
	if (n ==3) {
        
        closest_pair.a=DOT[0];
        closest_pair.b=DOT[1];
        closest_pair.dis=dist(DOT[0],DOT[1]);
        
        if(dist(DOT[1],DOT[2])<closest_pair.dis){
            closest_pair.a=DOT[1];
            closest_pair.b=DOT[2];
            closest_pair.dis=dist(DOT[1],DOT[2]);

        }
        if(dist(DOT[0],DOT[2])<closest_pair.dis){
            closest_pair.a=DOT[0];
            closest_pair.b=DOT[2];
            closest_pair.dis=dist(DOT[0],DOT[2]);
        }
            
      return closest_pair;

    }
		dot* temp1;
		dot* temp2;
		dot* ymid;

		int i, j;

		int num_ymid;
		if (n % 2 == 0) {
			temp1 = (dot*)malloc((n / 2) * sizeof(dot));
			temp2 = (dot*)malloc((n / 2) * sizeof(dot));
			for (i = 0; i < (n / 2); i++) {
				temp1[i] = DOT[i];
				temp2[i] = DOT[i + (n / 2)];

			}

			left_pair = Closest_Pair_DC(temp1, n / 2);
			right_pair = Closest_Pair_DC(temp2, n / 2);

			free(temp1);
			free(temp2);
		}
		else {
			temp1 = (dot*)malloc((n / 2) * sizeof(dot));
			temp2 = (dot*)malloc(((n / 2) + 1) * sizeof(dot));
			for (i = 0; i < (n / 2); i++) {
				temp1[i] = DOT[i];

			}
			for (i = 0; i <= (n / 2); i++) {
				temp2[i] = DOT[i + (n / 2)];
			}

			left_pair = Closest_Pair_DC(temp1, n / 2);
			right_pair = Closest_Pair_DC(temp2, (n / 2) + 1);
			free(temp1);
			free(temp2);
		}

		if (left_pair.dis >= right_pair.dis) closest_pair = right_pair;
		else closest_pair = left_pair;

		ymid = (dot*)malloc(n * sizeof(dot));

		left_num = DOT[n / 2].x;
		right_num = DOT[n / 2 + 1].x;


		for (i = 0, num_ymid = 0; i < n; i++) {

			if (DOT[i].x >= left_num - closest_pair.dis || DOT[i].x <= right_num + closest_pair.dis) {
				ymid[num_ymid] = DOT[i];
				num_ymid++;
			}

		}//ymid채우기
		num_ymid--;

		Sort_by_X_or_Y(ymid, 0, num_ymid, 1);


		for (i = 0; i < num_ymid - 1; i++) {
			for (j = i + 1; j < num_ymid && j <= i + 15; j++) {
				temp_num = dist(ymid[i], ymid[j]);
				if (temp_num <= closest_pair.dis) {
					closest_pair.dis = temp_num;
					closest_pair.a = ymid[i];
					closest_pair.b = ymid[i + 1];
				}
			}
		}
        free(ymid);

		return closest_pair;
	



}

int main()
{
	int tri;
	int i, j;
	int x_1, y_1;
	int THR, N;
	pair closest_pair;

	dot* DOT;


	scanf("%d", &N);




	DOT = (dot*)malloc(N * sizeof(dot));



	for (i = 0; i<N; i++) {
		scanf("%d%d", &x_1, &y_1);

		DOT[i].id = i;
		DOT[i].x = x_1;
		DOT[i].y = y_1;



	}



	tri = 0;//tri가 0이면 x정렬, 1이면 y정렬
	Sort_by_X_or_Y(DOT, 0, N - 1, tri);
	closest_pair = Closest_Pair_DC(DOT, N);



	printf("%d", closest_pair.dis);

	free(DOT);


	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

80% 틀립니다 ㅠㅠㅠ 어떤 케이스가 미스인걸까요..

changco 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
