글 읽기 - C로 구현했는데 왜 틀린건지 모르겠습니다 ㅠㅠ

object1997 3년 전 0

구글링해서 나온 C++소스를 C로 바꾸면서 힙소트로 정렬을 했습니다

도대체 뭐가 틀린건지 모르겠습니다ㅠㅠ

#include

#include

#include

#include

#pragma warning(disable:4996)

typedef struct Point {

int x, y;

}Point;

typedef struct heapType {

int max;

int current;

Point* pData;

}Heap;

int value[1000001];

int max;

void HeapSort(Point value[], int cnt, int type);

Heap* createMinHeap(int max);

void insertMinHeap(Heap* H, Point element, int type);

Point deleteMinHeap(Heap* H, int type);

int dist(Point& p, Point& q) {

return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);

}

int min(int val1, int val2) {

int ret = val1;

if (ret > val2) ret = val2;

return ret;

}

int closet_pair(Point it[],int n) {

if (n == 2) return dist(it[0], it[1]);

if (n == 3) {

int ret=min(dist(it[0], it[1]), dist(it[1], it[2]));

ret = min(ret, dist(it[2], it[0]));

return ret;

}

int line = (it[n / 2 - 1].x + it[n / 2].x) / 2;

int d = min(closet_pair(it, n / 2), closet_pair(it + n / 2, n - n / 2));//여기 까진 왼쪽, 오른쪽 나눠서 재귀호출

Point* mid = (Point*)malloc(sizeof(Point) * n);

int midind = 0;

for (int i = 0; i < n; i++) {

int t = line - it[i].x;//중간으로 부터 이 점의 x 거리

if (t * t < d) mid[midind++] = it[i]; //거리가 min보다 작으면 담음.

}

HeapSort(mid, midind, 0);

//y에 대해서 mid를 정렬

for (int i = 0; i < midind - 1; i++) {//끝에서 2번째까지만?

for (int j = i + 1; j < midind && (mid[j].y - mid[i].y) * (mid[j].y - mid[i].y) < d; j++) {

d = min(d, dist(mid[i], mid[j]));

}

}

return d;

}

int main() {

//freopen("a.inp", "r", stdin);

//freopen("a.out", "w", stdout);

int n;

scanf("%d", &n);

Point* points = (Point*)malloc(sizeof(Point) * n);

for (int i = 0; i < n; i++) {

scanf("%d %d", &points[i].x, &points[i].y);

}

HeapSort(points, n,1);

int result = closet_pair(points, n);

printf("%d", result);

//fclose(stdin);

//fclose(stdout);

}

void HeapSort(Point value[], int cnt,int type) {

Heap* H = createMinHeap(cnt*2);

for (int i = 0; i < cnt; i++) {

insertMinHeap(H, value[i],type);

}

for (int i = 0; i < cnt; i++) {

value[i] = deleteMinHeap(H,type);

}

}

Heap* createMinHeap(int max) {

Heap* ret = (Heap*)malloc(sizeof(Heap));

ret->max = max;

ret->current = 0;

ret->pData = (Point*)malloc(sizeof(Point) * max);

return ret;

}

void insertMinHeap(Heap* H, Point element,int type) {

int i = ++H->current;

while ((i != 1) && element.x < H->pData[i / 2].x) {

if (type == 1) {

H->pData[i].x = H->pData[i / 2].x;

}

else {

H->pData[i].y = H->pData[i / 2].y;

}

i /= 2;

}

H->pData[i] = element;

}

Point deleteMinHeap(Heap* H,int type) {

Point pRet;

memset(&pRet, 0, sizeof(pRet));

if (H != NULL && H->current > 0) {

pRet = H->pData[1];

int i = H->current;

Point* last = &(H->pData[i]);

H->current--;

int parent = 1;

int child = 2;

while (child <= H->current) {

if (type == 1) {

if (child < H->current && H->pData[child].x>H->pData[child + 1].x) {

child++;

}

if ((*last).x <= H->pData[child].x) {//얘가 뭐하는건지 모르겠음ㅠ

break;

}

}

else {

if (child < H->current && H->pData[child].y>H->pData[child + 1].y) {

child++;

}

if ((*last).y <= H->pData[child].y) {//얘가 뭐하는건지 모르겠음ㅠ

break;

}

}

H->pData[parent] = H->pData[child];

parent = child;

child *= 2;

}

H->pData[parent] = *last;

//*last는 뭐야?= last가 가르키고 있는 노드 자체

//노드 복사하는 거임.

}

return pRet;

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C로 구현했는데 왜 틀린건지 모르겠습니다 ㅠㅠ

object1997 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말