hujub   2년 전

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

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

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

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

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

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

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

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

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

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

pl0892029   2년 전

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

pl0892029   2년 전

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

pl0892029   2년 전

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

hujub   2년 전

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

appa   2년 전

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

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

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

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

appa   2년 전

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

pl0892029   2년 전

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

hujub   2년 전

hongjun7 님 답변 감사합니다.

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

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

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

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

4

-100000000 0

100000000 0

0 -100000000

0 100000000

이렇게 들어가면

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

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

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

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

pl0892029   2년 전

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

appa   2년 전

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

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

hujub   2년 전

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

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

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

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

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

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

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

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

pl0892029   2년 전

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

hujub   2년 전

넵..

대각선 정렬할 때, 

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

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

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

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

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

pl0892029   2년 전

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

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

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

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

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

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

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

appa   2년 전

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

pl0892029   2년 전

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

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