글 읽기 - 1708 볼록껍질(convex hull) 도와주세요!!

dltmd1507 3년 전 0

몇 시간 동안 고민했는데 계속 틀렸다고 나오네요...

질문에 있는 예제들은 다 되고 제가 따로 테스트케이스를 만들어서 돌려봤는데도 되는데

어디에서 틀렸는지 알 수가 없네요ㅠㅠㅠㅠ

고수님들 제발제발 도와주세요....

#include <stdio.h>
#include <stdlib.h>

struct v {
	long long x;
	long long y;
}ver[100000];

int compare(const void *A, const void *B)
{
    struct v* ptrA = (struct v*)A;
    struct v* ptrB = (struct v*)B;

    if (ptrA->y < ptrB->y)	return -1;
	if (ptrA->y > ptrB->y)	return 1;
	if (ptrA->x < ptrB->x)	return -1;
	if (ptrA->x > ptrB->x)	return 1;
}

int comparesin(const void *A, const void *B)
{
    struct v* ptrA = (struct v*)A;
    struct v* ptrB = (struct v*)B;

	if ((ptrA->x) * (ptrB->y) > (ptrA->y) * (ptrB->x))	return -1;
	if ((ptrA->x) * (ptrB->y) < (ptrA->y) * (ptrB->x))	return 1;
	if (ptrA->y < ptrB->y)	return -1;
	if (ptrA->y > ptrB->y)	return 1;
}

int ccw(int f, int s, int n)
{
	long long vector1x = ver[s].x - ver[f].x;
	long long vector1y = ver[s].y - ver[f].y;
	long long vector2x = ver[n].x - ver[s].x;
	long long vector2y = ver[n].y - ver[s].y;

	if((vector1x * vector2y - vector2x * vector1y) > 0)	return 1;
	else	return 0;
}

int main(void)
{
	int N;
	scanf("%d", &N);
	
	int i, j;
	for(i=0;i<N;i++)
		scanf("%lld %lld", &ver[i].x, &ver[i].y);

	// y 가 작은순, y가 같다면 x가 작은순으로 정렬
	qsort(ver, N, sizeof(struct v), compare);

	// y가 가장작은 점을 (0,0)으로 옮기고
	// 다른 점들도 그것에 맞게 옮긴다.
	for(i=1;i<N;i++)
	{
		ver[i].x -= ver[0].x;
		ver[i].y -= ver[0].y;
	}
	ver[0].x = 0;
	ver[0].y = 0;

	// +x축을 기준으로 반시계 방향으로 정렬
	qsort(&ver[1], N - 1, sizeof(struct v), comparesin);

	// stack을 이용하여 graham scan을 적용
	int stack[100000] = {0,1,};
	int stackpointer = 2;
	for(i=2;i<N;i++)
	{
		int de = 0;
		for(j=0;j<N;j++)
		{
			if(stackpointer-j-2 < 0)	break;
			if(!ccw(stack[stackpointer-j-2], stack[stackpointer-j-1], i))	de++;
			else break;
		}
		stackpointer -= de;
		stack[stackpointer] = i;
		stackpointer++;
	}

	printf("%d\n", stackpointer);

	return 0;
}

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

문제

문제

출처

ICPC

1708 볼록껍질(convex hull) 도와주세요!!

dltmd1507 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말