zasxer   2달 전

직사각형의 개수가 10만개, 왼쪽 아래 오른쪽 위의 좌표를 준다.(사각형끼리 같은 x또는 y좌표가 같은 경우가 없다.)

이 때 나올 수 있는 도형의 개수와 도형 중 최대 넓이는?? 도형은 정해진 모양이 없고 도형 안에는 단 한개의 선이 지나서는 안된다.

어떻게 구해야 할까요???

temp   2달 전

쉬운데..이거 비슷한 문제도 백준어딘가에있을겁니다..

힌트는 플레인스윕

zasxer   2달 전

플레인 스윕으로 하기에는 직사각형의 개수가 10만개인데 x, y 좌표가 20만개 씩 나오는데

도형은 직사각형의 넓이의 최댓값이 아니고 6각형 10각형도 나올 수 있는데 이 넓이들은 어떻게 구해야하나요?


temp   2달 전

흠 그런문제가있군요. 다안읽었네요 ㅋㅋㅋ

우선 플레인스윕으로 풀라는게아니라, 이걸 보다보면 우선순위큐와 무슨 알고리즘이었는지 정확히 기억이 안나는데 그거 활용하면 시간을 상당히 단축시켜서 20만개도 충분하구요. 넓이를 구하라는게아니라 이걸 통해서 개수를 구할수있어집니다. 사각형이 몇개인지. 근데 사각형이 아니라 정해진모양이없다면 더 생각을 해봐야겠네욤 ㅎㅎ


yukariko   2달 전

제 생각엔 매우 어려운 문제인것 같습니다. 단순한 플레인 스위핑으론 불가능해보이네요.

temp   2달 전

동감합니다. 제가 생각이 짧았어요 ㅠㅠ


문제를 제대로 안읽었더니...

zasxer   2달 전

최적화 문제인 거 같은데....

small test case와 medium test case는 먼가 손 댈 수 있을 거 같은데...

large test case는 수치도 크고...

추가적으로 답은 int범위 내이고

case 하나당 약 10초정도까지 쓸 수 있을 거 같습니다.

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