직사각형

직사각형

문제

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 

직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다.

 

 

 

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x＜p, y＜q 이다. 

예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다.

먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

 

 

또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다.

 

마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

 

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다.

 

 

입력형식

모든 입력파일은 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사각형의 좌표 값은 1이상 50,000 이하의 정수로 제한된다.

 

출력형식

여러분은 입력파일 4개의 각 줄에 주어진 두 직사각형의 공통부분을 조사해서 해당하는 코드 문자를 출력파일의 첫 4개의 줄에 각각 차례대로 출력해야 한다.

 

입력 예

3 10 50 60 100 100 200 300
45 50 600 600 400 450 500 543
11 120 120 230 50 40 60 440
35 56 67 90 67 80 500 600

출력 예

d

a

a

b

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

struct rect {
    int x1, y1, x2, y2;
} rect1, rect2;
int x[4], y[4];

int comp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int is_overlap(int a, int b, int c, int d) {
    return !((b <= c) || (d <= a));
}

int main() 
{
    int i, j, k, res;

    for (k = 0; k < 4; k++)
    {
        scanf("%d %d %d %d %d %d %d %d", &rect1.x1, &rect1.y1, &rect1.x2, &rect1.y2, &rect2.x1, &rect2.y1, &rect2.x2, &rect2.y2);
        x[0] = rect1.x1;
        x[1] = rect1.x2;
        x[2] = rect2.x1;
        x[3] = rect2.x2;

        y[0] = rect1.y1;
        y[1] = rect1.y2;
        y[2] = rect2.y1;
        y[3] = rect2.y2;

        qsort(x, 4, sizeof(x[0]), comp);
        qsort(y, 4, sizeof(y[0]), comp);

        //오버랩되는 경우
        res = -1;
        for (i = 0; i < 3; i++) {
            if (x[i] == x[i + 1])
                continue;
            for (j = 0; j < 3; j++) {
                if (y[j] == y[j + 1])
                    continue;

                if (rect1.x1 <= x[i] && x[i + 1] <= rect1.x2 && rect1.y1 <= y[j] && y[j + 1] <= rect1.y2
                    && rect2.x1 <= x[i] && x[i + 1] <= rect2.x2 && rect2.y1 <= y[j] && y[j + 1] <= rect2.y2)
                    res = 0;
            }
        }

        if (res == 0) {
            printf("a\n");
            continue;
        }

        // 점끼리 만나는 경우
        if ((rect1.x2 == rect2.x1 && rect1.y2 == rect2.y1) || (rect1.x2 == rect2.x1 && rect1.y1 == rect2.y2)
            || (rect1.x1 == rect2.x2 && rect1.y1 == rect2.y2) || (rect1.x1 == rect2.x2 && rect1.y2 == rect2.y1)) {
            printf("c\n");
            continue;
        }

        // 선끼리 만나는 경우
        if ((rect1.y1 == rect2.y2 && is_overlap(rect1.x1, rect1.x2, rect2.x1, rect2.x2)) 
            || (rect1.y2 == rect2.y1 && is_overlap(rect1.x1, rect1.x2, rect2.x1, rect2.x2))
            || (rect1.x2 == rect2.x1 && is_overlap(rect1.y1, rect1.y2, rect2.y1, rect2.y2))
            || (rect1.x1 == rect2.x2 && is_overlap(rect1.y1, rect1.y2, rect2.y1, rect2.y2))) {
            printf("b\n");
            continue;
        }

        printf("d\n");
    }

    return 0;
}