글 읽기 - 반례를 알 수 있을까요?

asphodel1997 5년 전 0

테스트 케이스는 1개에 불과하지만, 일단 테스트 케이스는 OK입니다.

그런데, 제출하면 "틀렸습니다"입니다.

반례를 알 수 있을까요?

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

//#define DBG(fmt, ...)       printf(fmt, ##__VA_ARGS__)
#define DBG(fmt, ...)       do{}while(0)

#define FOR(i, from, to)        for(int i = (from); i < (to); i++)
#define FOR_EQ(i, from, to)     for(int i = (from); i <= (to); i++)

#define MAX_N   30004
#define WHITE   0
#define BLACK   1

typedef struct coord {
	int x;
	int y;
} coord_t;

int ANSWER_MAX, ANSWER_MIN;

///////////////////////////////////////////////////////////////////////////////////////////////
#define MAX_NODE	(MAX_N)

typedef struct listNode
{
	coord_t point;
	struct listNode* prev;
	struct listNode* next;
} ListNode;

typedef struct
{
	ListNode node;
} ListNodeHeap;

/***/
typedef struct square {
	coord_t start;
	coord_t end;
} square_t;

typedef struct queue {
	ListNode* list;
	int num;
} queue_t;
/***/

ListNodeHeap heap[MAX_NODE];
int heap_cursor;

void initHeap(void)
{
	heap_cursor = 0;
}

void initListNode(ListNode* node)
{
	node->prev = node;
	node->next = node;
}

ListNode* getListNode(void)
{
	int i = heap_cursor++;

	initListNode(&heap[i].node);
	return &heap[i].node;
}

ListNode* appendListNode(ListNode* list, ListNode* node)
{
	//ListNode* node = getListNode();
	//node->data = data;
	
	if (list == NULL)
	{
		return node;
	}
	else
	{
		ListNode* last = list->prev;
		last->next = node;
		list->prev = node;
		node->prev = last;
		node->next = list;
		return list;
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////

/*
1. 사각형, 사각형 색깔, 사각형 안에 포함된 모든 점을 전달 받고, 사각형 색깔에 따라, 첫번째 점 기준으로 수평 또는 수직으로 자른다. 
   그러면 이제 2개의 사각형이 되었다. 그리고 점들도 2개의 그룹으로 구분되었다.
*/
void dfs(square_t *curRect, int color, queue_t *queue)
{
	square_t nextRect;
	int x, y;

	queue_t topPoint;
	queue_t downPoint;
	queue_t rightPoint;
	queue_t leftPoint;

	ListNode *nodeCur, *nodeNext;

	int width, height;
	int size;

	/* termination */
	if (!queue->list || queue->num == 0)
	{
		width = curRect->end.x - curRect->start.x;
		height = curRect->end.y - curRect->start.y;
		size = width * height;

		DBG("%d\n", size);

		if (size < ANSWER_MIN)
			ANSWER_MIN = size;

		if (ANSWER_MAX < size)
			ANSWER_MAX = size;

		return;
	}

	/* current */
	nodeCur = queue->list;
	x = nodeCur->point.x;
	y = nodeCur->point.y;

	/* next */
	//horizontal
	if (color == WHITE)
	{
		topPoint.list = NULL;
		topPoint.num = 0;
		downPoint.list = NULL;
		downPoint.num = 0;

		/**/
		nodeCur = nodeCur->next;

		FOR(i, 1, queue->num)
		{
			nodeNext = nodeCur->next;

			if (y < nodeCur->point.y)
			{
				topPoint.list = appendListNode(topPoint.list, nodeCur);
				topPoint.num++;
			}
			else if (nodeCur->point.y < y)
			{
				downPoint.list = appendListNode(downPoint.list, nodeCur);
				downPoint.num++;
			}

			nodeCur = nodeNext;
		}

		//topPoint
		nextRect.start.x = curRect->start.x;
		nextRect.start.y = y;
		nextRect.end.x = curRect->end.x;
		nextRect.end.y = curRect->end.y;
		dfs(&nextRect, BLACK, &topPoint);

		//downPoint
		nextRect.start.x = curRect->start.x;
		nextRect.start.y = curRect->start.y;
		nextRect.end.x = curRect->end.x;
		nextRect.end.y = y;
		dfs(&nextRect, BLACK, &downPoint);
	}
	//vertical            
	else
	{
		rightPoint.list = NULL;
		rightPoint.num = 0;
		leftPoint.list = NULL;
		leftPoint.num = 0;

		/**/
		nodeCur = nodeCur->next;

		FOR(i, 1, queue->num)
		{
			nodeNext = nodeCur->next;

			if (x < nodeCur->point.x)
			{
				rightPoint.list = appendListNode(rightPoint.list, nodeCur);
				rightPoint.num++;
			}
			else if (nodeCur->point.x < x)
			{
				leftPoint.list = appendListNode(leftPoint.list, nodeCur);
				leftPoint.num++;
			}

			nodeCur = nodeNext;
		}

		//rightPoint    
		nextRect.start.x = x;
		nextRect.start.y = curRect->start.y;
		nextRect.end.x = curRect->end.x;
		nextRect.end.y = curRect->end.y;
		dfs(&nextRect, WHITE, &rightPoint);

		//leftPoint    
		nextRect.start.x = curRect->start.x;
		nextRect.start.y = curRect->start.y;
		nextRect.end.x = x;
		nextRect.end.y = curRect->end.y;
		dfs(&nextRect, WHITE, &leftPoint);
	}
}

int main(int argc, char* argv[])
{
	int width, height;
	int n;
	square_t firstRect;
	queue_t firstPoint;
	ListNode* node;

	freopen("2574.txt", "r", stdin);

	initHeap();

	//최초 사각형
	scanf("%d %d", &width, &height);

	firstRect.start.x = 0;
	firstRect.start.y = 0;
	firstRect.end.x = width;
	firstRect.end.y = height;

	//최초 점들의 리스트
	firstPoint.list = NULL;
	firstPoint.num = 0;

	scanf("%d", &n);
	FOR(i, 0, n) 
	{
		node = getListNode();
		scanf("%d %d", &node->point.x, &node->point.y);
		firstPoint.list = appendListNode(firstPoint.list, node);
	}
	firstPoint.num = n;

	ANSWER_MAX = 0;
	ANSWER_MIN = width * height;
	dfs(&firstRect, WHITE, &firstPoint);

	printf("%d %d\n", ANSWER_MAX, ANSWER_MIN);

	return 0;
}

Green55 5년 전 0

혹시 freopen 빼셨나요?

asphodel1997 5년 전 0

네 freopen은 주석처리했습니다.

소스 복사할 때, 주석처리 부분이 사라졌네요^^

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

문제

문제

출처

ICPC

반례를 알 수 있을까요?

asphodel1997 5년 전 0

Green55 5년 전 0

asphodel1997 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말