입력 : N 개의 직사각형. 직사각형의 좌표가 주어집니다.주어진 사각형이 정사각형을 형성하는지 확인하기 위해 Algo
출력 : 사각형을 형성하는지 여부를 확인합니다.
I 직사각형은 X 및 Y 축에 평행되는 경우를 해결했다.
SOLN : 사각형의 영역 이후
, 그래서 완벽한 정사각형 (총 사각형의 면적의 합 - 그들 사이에 겹치는)는 정사각형이어야한다.
이제 분을 찾으십시오. 의 값 X 모든 직사각형의 좌표 및 최대. Y 값 좌표입니다. 사각형을 형성하는 경우 | min (x) - max (y) |은 사각형의 길이입니다. 이제 겹침을 고려한 사각형 영역의 합계를 찾습니다. 길이가 사각형의 면적과 같으면 | min (x) - max (y) |. 빙고 !!
복잡성 : O (N *의 않음) 일반적인 경우에 대한 해결 방법
?
모든 직사각형이 정사각형을 형성하지만 직사각형의 모서리가 축과 평행하지 않다고 가정합니다.
그런 다음 정사각형에는 4 개의 정점이 있습니다 (상단, 하단, 오른쪽 및 왼쪽). 사각형의 상단 정점은 모든 직사각형의 모든 정점의 y 좌표의 y 좌표 = max를가집니다. 다른 세 개의 꼭지점 : bottom (최소 y), right (최대 x), left (최소 x).
사각형의 각을 찾으려면 두 개의 꼭지점 인 아래쪽과 오른쪽 만 있으면 충분합니다. 아래쪽의 정점 좌표는 (someX, minY)이고 오른쪽 정점 좌표는 (maxX, someY)입니다. 그러면 각도는 atan((someY-minY)/(maxX-someX))입니다. C/C++/Java/C#에서는 atan2 함수를 사용할 수 있습니다.
다음으로 모든 직사각형을 -angle에 회전하면 축에 대해 평행 한 직사각형에 알고리즘을 적용 할 수 있습니다.
로고가없는 경우 O (N^2) 솔루션을 이미 가지고 계신다면 Mark의 대답은 정확합니다. 그러나이 문제의 가장 어려운 부분은 사실상 회전이없는 경우입니다 (정확한 겹침 부분을 찾는 것).
나는 여러 중복 (2 개 이상 사각형이 한 자리에 중복)의 경우를 고려하면 잘 모르겠지만, 중복 영역을 찾는 것에 대해 궁금해하는 사람들을 위해 :
는흥미로운 청소 알고리즘이 존재 함 일부 데이터 구조를 사용하여 O (N log N)로 조정할 수 있습니다.
확인 당신이 관심이 있다면이 링크 : Efficient algorithm to find Area of Overlapping Rectangles
O (N)에서이 작업을 수행 할 수 있습니다. 최종 사각형의 변을 구성하는 사각형의 변은 Y-intercept이고 가장 작은 것이 X-intercept입니다. 가장 작은 X 및 Y 절편을 만드는면을 추적하여 최종 경계의 일부인면을 식별 할 수 있습니다.
가장 작은 요격 장치 제조업체로 인정되는 모든 측면은 라인을 따라 최소/최대 값에 대해 테스트되고 해당 값이 업데이트됩니다.
마지막으로 min-Y 절편과 min-X 절편 사이의 최소 최대 간격을 비교하고 길이가 동일한 경우 최종 경계는 정사각형입니다.
명확하지 않은 경우 의사 코드를 제공 할 수 있습니다. 알려줘. 아래에 그림을 추가했습니다. 
사각형에 간격이 없음을 보장하지 않습니다. – chris544
직사각형의 크기와 좌표는 얼마나됩니까? – chris544