최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드

난이도 ★★★★☆

문제를 보시려면 여기를 클릭

틀리기 쉬운 입출력 예제

입력	출력
3 4 10000 -10000 -10000 10000 10000 10000 -10000 -10000 7 2 2 2 4 5 4 5 1 1 1 1 2 2 1 8 7 19 11 15 3 11 3 15 7 11 11 11 3 19 11 19	20000 20000 1 3 8 8

힌트

정사각형을 만드는 네 점을 잡았다면, 그 네 점은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이런 형태이다.  → 따라서 같은 값이 하나도 없는 좌표는 탐색할 필요가 없다. 같은 값이 최소 1개 이상 있는 것만 탐색한다.

이하는 코드입니다. (내 생에 최다의 for문 중첩. 무려 7중)

#include <stdio.h>
#include <vector>
#include <algorithm>
 
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int x;
    int y;
}Point;
 
bool myCompareX(const vector<Point> left, const vector<Point> right) {
    return left[0].x < right[0].x;
}
 
bool myCompareY(const Point left, const Point right) {
    return left.y < right.y;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
    
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get points
        vector<vector<Point>> points;
        for (int i = 0; i < N; i++) {
            Point *point = new Point;
 
            scanf("%d %d", &point->x, &point->y);
 
            bool found = false;
            for (int j = 0; j < points.size(); j++) {
                if ((points[j].size() > 0) && (points[j][0].x == point->x)) {
                    points[j].push_back(*point);
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                vector<Point> *arr = new vector<Point>;
                arr->push_back(*point);
                points.push_back(*arr);
            }
        }
 
        // trim
        for (int i = 0; i < points.size(); i++) {
            if (points[i].size() < 2) {
                points.erase(points.begin() + i);
            }
        }
 
        // sort
        for (int i = 0; i < points.size(); i++) {
            sort(points[i].begin(), points[i].end(), myCompareY);
        }
        sort(points.begin(), points.end(), myCompareX);
 
        /* find min, max */
        int minLength = 20001, maxLength = 0;
 
        for (int i = 0; i < points.size() - 1; i++) {
            // get x
            for (int j = 0; j < points[i].size() - 1; j++) {
                // (x, y1)
                int y1 = points[i][j].y;
                for (int k = j + 1; k < points[i].size(); k++) {
                    // (x, y2)
                    int y2 = points[i][k].y;
                    int length = y2 - y1;
                    int nextX = points[i][0].x + length;
 
                    // find nextX
                    for (int l = i + 1; l < points.size(); l++) {
                        // nextX found
                        if (points[l][0].x == nextX) {
                            for (int m = 0; m < points[l].size() - 1; m++) {
                                // y1 found
                                if (points[l][m].y == y1) {
                                    for (int n = m + 1; n < points[l].size(); n++) {
                                        // Finally, y2 found
                                        if (points[l][n].y == y2) {
                                            minLength = MIN(minLength, length);
                                            maxLength = MAX(maxLength, length);
                                            break;
                                        }
 
                                        // y2 not found
                                        if (points[l][n].y > y2) {
                                            break;
                                        }
                                    }
                                    break;
                                }
 
                                // y1 not found
                                if (points[l][m].y > y1) {
                                    break;
                                }
                            }
                            break;
                        }
 
                        // nextX not found
                        if (points[l][0].x > nextX) {
                            break;
                        }
                    }
                }
            }
        }
 
        // print
        printf("%d %d\n", minLength, maxLength);
    }
 
    return 0;
}