글 읽기 - 어휴...직사각형 최대넓이 문제 질문있습니다..

hujub 9년 전 0

이거 왜 틀렸는지 도저히 모르겠네요.

입력데이터 만들고 printf 로 단계단계 출력하면서 분석까지 해봤는데..

도저히 제 힘만으로는 알수가 없네요.

보시다가 논리적인 오류나 반례같은 것 발견하시면 말씀해주세요ㅠㅠ

참고로 어떻게 풀었는지 대략적으로 말씀드리자면

각 점사이의 기울기 값들을 다 저장해놓고 정렬시켰습니다.

그리고 더블포인터로 90도가 되는 지점들을 골라낸 후 네 번째 점을 구해서

이 점이 존재하는지 안하는지 확인을 했습니다. 만약 존재한다면 넓이를 업데이트 시키고

최종 답을 출력하는 형태입니다... (밑에 홍준님 게시물에서 pichulia 님이 설명하셨던 방식)

코드가 약간 조잡해서 주석처리 했습니다.. 답변부탁드립니다.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

#define dnum	1501

#define mulnum	1
#define INF		1000000007
#define	empty	-1000000007

using namespace std;

int x[dnum],y[dnum],mst[dnum],pst[dnum],Rank[dnum][dnum];
int i;

double gradient[dnum][dnum];

vector <double> area;
vector <int> x4,y4,rightangle;

int cmp(int k, int j)
{
	return (gradient[i][k] < gradient[i][j]);
	// 기울기를 비교해서 Rank 를 정렬
}

double dist(int diffx, int diffy)
// 두점 사이의 거리 구하는 함수
{
	return (double)sqrt(((double)diffx*diffx)+(double)diffy*diffy);
}

int main()
{
	int N;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d%d", &x[i], &y[i]);

	// N, x, y 입력 받음

	for (i = 0; i < N; i++)
	// x[i],y[i] 를 기준으로
	{
		for (int j = 0; j < N; j++)	//x[j],y[j] 를 비교함
		{
			if(x[i] == x[j])
			// 비교되는 두 점의 x좌표가 같다면,
			{
				if(i != j)
				// 그리고 i 와 j 가 같은 값이 아니라면
					gradient[i][j] = INF;
					// 기울기가 무한대임, 왜냐하면 두 점의 x차이가 0 이기 때문 (INF = 1000000007)
				else
				// i 와 j 가 같다면
					gradient[i][j] = empty;
					// 같은 점이므로 empty ( = -1000000007) 대입
			}
			else
			// 두 점의 x좌표가 다르다면,
			{
				gradient[i][j] = (((double)(y[j] - y[i]))/((double)(x[j] -x[i])));
				// 두 점 사이 기울기 정보를 담고있는 gradient 에 기울기를 계산해서 저장
			}
		}
        
        for (int j = 0; j < N; j++)
			Rank[i][j] = j;
			// gradient 를 오름차순으로 탐색하기 위한 Rank 배열을 초기화 

		sort(Rank[i] , Rank[i] + N, cmp);
		// gradient 를 비교해서 Rank 를 정렬

		int tmp = 0;
		// 0 과 음수인 기울기를 양수인 기울기와 구분하기 위한 인덱스 변수

		// 음수기울기와 양수 기울기를 구분하는 이유
		// 음수 기울기와 양수기울기를 곱해서 -1이 되는 포인트(직각을 이루는 점들을)를 찾기위해서

		for (int j = 0; j < N; j++)
		{
			if(gradient[i][Rank[i][j]] <= 0)
			// 오름차순으로 쭉 탐색하면서 기울기가 음수이거나 0 인 경우
				tmp = j;
				// tmp 에 j (위치)를 저장 그리고 for문 돌리는 동안 계속 업데이트
			else
			// 양수의 기울기를 만났으면
				break;
				// for문을 빠져나옴
		}
		
		if(tmp != 0)
		// tmp 가 0이 아니라면, 즉, 음수의 기울기나 0인 기울기가 존재한다면
		{
			pst[i] = tmp + 1;
			// plus start 배열(양수의 기울기)은 tmp + 1 지점부터 시작됨
			mst[i] = 1;
			// minus start 배열(음수의 기울기)은 1부터 시작 (인덱스 0은 empty 값이 저장돼있음)
		}
	}

	for (int i = 0; i < N; i++)
	// 점의 개수 만큼 반복
	{
		if(mst[i] == 0 || pst[i] >= N)
		// gradient[i][] 에 음수의 기울기가 없거나 양수의 기울기가 존재하지 않는다면
			continue;
			// 다시 올라감, 
			// 왜냐하면 두 기울기를 곱해서 -1이 될 때, 90도를 이루는데, 이 때는 음수와 양수가 공존해야하기 때문

		int pos = pst[i];
		// pos 에 plus start 되는 지점을 저장

		for (int k = mst[i]; k < pst[i]; k++)
		// k 가 마이너스가 시작되는 지점부터 양수의 기울기가 나오기 직전까지 반복 증가됨
		{
			int j = Rank[i][k];
			// 이 k 는 Rank 배열의 인덱스임, gradient 에 써먹기위해 j 로 Rank[i][k] 를 대입

			if(gradient[i][j] == 0)
			// 기울기가 0이 되는 지점을 만났을 때,
			{
				while(pos < N && gradient[i][Rank[i][pos]] < INF)
				// 기울기가 무한대가 되기 직전까지
				{
					pos++;
					// pos 를 증가시킴 (더블포인터)
				}

				int tmp = pos;
				// gradient[i][j] 와 직각을 이룰 수 있는 여러 값들을 찾기위한 인덱스 변수
				// pos 값은 static 해야 되므로 tmp 라는 값에 대입, 임시변수

				while(tmp < N && gradient[i][Rank[i][tmp]] == INF)
				// 기울기가 무한대인 곳을 만났거나 만나는 동안
				{
					rightangle.push_back(tmp);
					// 직각 이라는 벡터에 Rank 인덱스를 저장
					tmp++;
					// tmp 를 증가시킴
				}

				if(rightangle.size() == 0)
				// 직각(rightangle) 벡터에 아무것도 저장하지 못했다면, 즉, 직각을 이루는 기울기가 존재하지 않는다면
					continue;
				// 올라감
			}
			else
			// 0이 아닌 음수의 기울기를 만났다면
			{
				while(pos < N && gradient[i][j]*gradient[i][Rank[i][pos]] > -1)
				// 음수기울기와 양수기울기를 곱했을 때, -1 보다 큰값을 만나는 동안
				{
					pos++;
					// pos 를 증가시킴 (더블포인터)
				}

				int tmp = pos;
				// 위와 마찬가지로 임시인덱스 변수

				while(tmp < N && gradient[i][j]*gradient[i][Rank[i][tmp]] == -1 )
				// 음수기울기와 양수기울기를 곱했을 때, -1이 되는 경우를 만났거나, 만나는 동안
				{
					rightangle.push_back(tmp);
					// 그 경우들, 인덱스를 직각 벡터에 저장
					tmp++;
				}

				if(rightangle.size() == 0)
				// 직각벡터가 비어있다면
					continue;
					// 다시 위로 올라감
			}

			for (int h = 0; h < rightangle.size(); h++)
			// 직각 벡터의 크기 만큼 반복
			{
				int R_pos = Rank[i][rightangle[h]];
				// 직각이 되는 인덱스를 Rank 배열에 집어넣어서 x,y 배열에 사용함
			
				x4.push_back(x[j] + x[R_pos] - x[i]);
				y4.push_back(y[j] + y[R_pos] - y[i]);

				// 예상되는 네 번째 점을 구해서 x4,y4 벡터에 대입

				area.push_back(dist(x[R_pos]-x[i],y[R_pos]-y[i])*dist(x[j]-x[i],y[j]-y[i]));
				// 넓이도 area 에 대입
			}
			
			rightangle.clear();
			// 직각 벡터 비움
		}
	}

	double ans = 0;
	// 최종 답 변수

	// 아래는 예상되는 네 번째 점이 x , y 배열에 존재하는지 확인하는 과정
	// 만약에 존재한다면 넓이값을 업데이트
	for (int i = 0; i < x4.size(); i++)
	{
		for (int j = 0; j < N; j++)
		{
			if(x[j] == x4[i] && y[j] == y4[i])
			{
				if(ans < area[i])
					ans = area[i];
			}
		}
	}

	printf("%0.lf\n",ans);
	// 최종답 출력

	return 0;
}

pl0892029 9년 전 0

음.... TC를 찾아서 보셔도 되고 더블릿에서 채점 받으시면 친절하게 (?) 알 수 있다죠 ㅋㅋ

pl0892029 9년 전 0

제 눈에 보이는건 기울기가 10억 7보다 큰 경우가 존재할수도 있지 않나요..?

pl0892029 9년 전 1

위에 글은 뻘글이네요 -_-... 자삭하긴 귀찮고... 대신 좀더 코드 자세히 살펴보겠습니다.

hujub 9년 전 0

답변 감사합니다ㅎㅎㅎ 근데 TC 는 뭔가요?

h0ngjun7 9년 전 0

우선, 기울기가 무한대일 경우는 +무한대인 경우와 -무한대인 경우 2가지 모두를 고려해주어야할 것 같습니다.

기울기가 0이되는데 +0이 될 수도 있고 -0이 될 수도 있으니까요.(마찬가지로 0인 것도 둘 다 고려해주어야하죠. 0인 것은 입실론을 잘 쓰시면 됩니다.)

그리고 정수좌표로 출력해주는 과정에서 실수오차가 생길 수 있기 때문에 1e-5~1e-7 정도를 더해주는 것이 좋습니다.

(디버깅하다보면 1을 0.9999999999999와 같이 저장하더라구요.)

h0ngjun7 9년 전 0

사실 기울기가 0인 경우랑 무한대인 경우는 따로 분리하는 게 처리하기 편합니다.

pl0892029 9년 전 0

TC는 테스트케이스를 뜻합니다. 어느 경우에 반례가 있는지 납득이 안될땐 예제를 돌려보면 쉽게 이해되는 경우가 종종 있죠 ㅋ

hujub 9년 전 0

hongjun7 님 답변 감사합니다.

그런데.. +무한대, -무한대가 어떤 의미가 있는지는 아직 잘 모르겠습니다.

그러니깐, x1-x2 가 딱 0이면 이게 +쪽 무한대인지 -쪽 무한대인지

어떻게 구분가능한지 모르겠어요... 그 부분은.. 좀 더 생각해봐야 될것 같구요.

그리고 반례를 하나 제가 찾은것 같은데요.

-100000000 0

100000000 0

0 -100000000

0 100000000

이렇게 들어가면

값이 20000000.....004 이렇게 나오네요..

딱 20000000...000 이런식으로 떨어져야되는데 그렇게 안나오네요

이 부분으로는 혹시 기술적인 방안이 있으신지 궁금합니다.

이걸 해결하기위해 1e-5 같은것을 사용하는 건가요?

pl0892029 9년 전 0

위에서 적으신 얘기는 double을 써서 발생하는 문제 같은데, long long을 쓰면 소수점 연산을 피할 수 있지 않나요?

h0ngjun7 9년 전 0

long long을 쓰면 sqrt연산을 못하기 때문에 제곱의 합을 들고있어야하는데, 넓이를 계산할 떄 long long 범위를 초과하게 됩니다.

double 실수 연산을 잘해줘야되는 거 같아요.

hujub 9년 전 0

휴... hongjun7 님 풀이 방식 처럼

대각선의 길이가 같다 그리고 두 대각선의 중점의 좌표가 같다 라는 특징을 가지고

대각선의 길이를 내림차순으로 정렬하고 특징을 이용한 조건으로 소스를 짰습니다.

인터넷에 찾아보니 여기 백준온라인저지 말고도 http://wcipeg.com/problem/rect1 여기에도 이 문제가 있더라구요.

그래서 거기에는 제출해보니 어셉을 받았는데.. 여기 백준저지에서는 시간초과가 뜨네요.. ㅠ

97% 까지 가놓고 시간초과가 뜨니깐 엄청 속터지네요 ㅋㅋㅋ

시간제한 1초 너무 짧은 시간 같습니다.ㅜ

어쨌든 알게모르게 도움 주신분들 감사합니다.

pl0892029 9년 전 0

@hujub 대각선을 이용해서 문제를 푸신다면, double 연산을 하지 않는 것으로 오차 제거 + 시간을 줄일 수 있습니다. ㅜㅜ 그리고 현재 보고있는 대각선의 길이의 제곱/2 의 값보다 현재 넓이가 크거나 같다면 더 이상 반복문을 돌지 않아도 됩니다. O(N^4) 솔루션이라도 이런 커팅을 이용하면 O(N^2 logN) 보다 빠르게 됩니다.

hujub 9년 전 0

넵..

대각선 정렬할 때,

if(대각선의 길이 제곱 < 2*Max 넓이)break;

이걸 넣었고 그리고 double 연산은 넓이 계산할 때만 사용했습니다.

https://www.acmicpc.net/source/302664

그런데 시간초과가 뜨네요.

다행이 제가 이 게시물에 올려놨던 기울기정렬법을 다시 한번 고쳐봤는데.. 이건 어셉을 받았습니다.

pl0892029 9년 전 2

@hujub double 연산을 피하는 방법이 다음과 같습니다.

4개의 x, y 좌표에서 minX, maxX, minY, maxY를 추려냅니다.

이 값들로 우리는 직사각형 넓이를 구할 수 있습니다.

각 좌표들을 시계방향/반시계방향으로 순회하며 이 직사각형과, 네 점이 이루는 모퉁이 삼각형들의 넓이를 빼줍니다.

그러면 남는 면적은 직사각형의 넓이가 됩니다.

그리고 대각선에 루트를 씌우지 마시고, long long 값을 그대로 가지고 있으세요. 대각선의 제곱된 길이 < 2×최대넓이 인데, 이 과정에서 대각선의 제곱된 길이 연산이 차지하는 비중이 꽤 커보입니다. 굳이 루트를 씌우지 않아도 해결되는 부분 같네요.

더 자세한 정보가 필요하시면 댓글 다시면 얘기해드리겠습니다.

h0ngjun7 9년 전 0

와! 이런 거 너무 좋아요! ㅎㅎ 아이디어들 많이 얻어갑니다~

pl0892029 9년 전 0

결론적으로 얘기하면 이 문제에서 sqrt나 double을 필수로 쓸 필요가 없습니다. 실수연산을 피할 수 있단게 꿀이죠 ㅋㅋ

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

문제

문제

출처

ICPC

어휴...직사각형 최대넓이 문제 질문있습니다..

hujub 9년 전 0

pl0892029 9년 전 0

pl0892029 9년 전 0

pl0892029 9년 전 1

hujub 9년 전 0

h0ngjun7 9년 전 0

h0ngjun7 9년 전 0

pl0892029 9년 전 0

hujub 9년 전 0

pl0892029 9년 전 0

h0ngjun7 9년 전 0

hujub 9년 전 0

pl0892029 9년 전 0

hujub 9년 전 0

pl0892029 9년 전 2

h0ngjun7 9년 전 0

pl0892029 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말