[더블릿 - 11] 직사각형/koi_rect

프로그램 명: koi_rect

제한시간: 1 초

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x,y) 와 오른쪽 위 꼭짓점 좌표 (p,q) 로 주어진다.

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

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

3 2 9 8

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

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

  

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

  

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

  

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

공통 부분의 특징	코드 문자
직사각형	a
선분	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

출처:2012 지역 본선 초등 3/5

두 직사각형을 어떻게 비교할것인가가 문제이다.

문제처럼 주어진 두 대각선 방향의 꼭지점 두 개로 비교 하려고 하면

꽤 지저분해질 것이다.

이걸 원과 비슷하게 생각하면 쉽다.

중학교 땐가 고등학교 땐가 원에 대해서 이런걸 배운다.

두 원의 중심간의 거리가

두 반지름의 함과 같으면 두 원은 접합

두 반지름의 합보다 작으면 두 원은 겹침

두 반지름의 합보다 크면 두 원은 만나지 않는다.

이 걸 응용해서

대각선 방향의 두 점으로 표현되어지는 사각형을

사각형의 중심점과 가로, 세로 방향으로 중심점으로부터의 거리로 바꿔 표현 할 수 있다.

그 다음 이걸 원과 비슷하게

두 사각형의 중심간의 거리와

가로 방향의 길이의 합과 세로 방향 길이의 합을 비교하면 쉽게

접함, 겹침을 비교할 수 있다.

#include <iostream>

#include <cmath>

#include <utility>

using namespace std;

 

const int n = 8;

int a[n];

 

struct Circle

{

    double x,y,h,v;

 

    Circle(int x1, int y1,int x2,int y2)

    {

        x = (x1 + x2)/2.0;

        y = (y1 + y2)/2.0;

        h = x2 - x;

        v = y2 - y;

    }

    void cmp(Circle c)

    {

        double xCom = abs(x - c.x) - (h + c.h);

        double yCom = abs(y - c.y) - (v + c.v);

        if (xCom == 0. || yCom == 0.)

        {

            if (xCom != 0. || yCom != 0.)

                cout << 'b';

            else

                cout << 'c';

 

        }

        else if (xCom < 0. && yCom < 0.)

            cout << 'a';

        else

            cout << 'd';

        cout << '\n';

    }

};

int main()

{

    for (int c = 0; c < 4; ++c)

    {

        for (int i = 0; i < n; ++i)

            cin >> a[i];

 

        Circle c1(a[0],a[1],a[2],a[3]), c2(a[4],a[5],a[6],a[7]);

        c1.cmp(c2);

    }

     

    return 0;

}