단순 사각형 - 4485

Algorithm/codeUp 2020. 2. 12. 23:47

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

//https://codeup.kr/problem.php?id=4458
 
#include <iostream>
using namespace std;
 
int arr[201][201];
 
void init()
{
    int y, x;
    cin >> y >> x;
    arr[2*x][2*y] = 3;
    int n; cin >> n;
    char c;
    int r;
    for(int i = 0; i<n; ++i)
    {
        cin >> c >> r;
        if(c == 'R')
        {
            for(int j = 2*y+1; j <= 2*(y+r); ++j)
                if(arr[2*x][j] == 0)
                    arr[2*x][j] = 1;
                else if(arr[2*x][j] == 2)
                    arr[2*x][j] = 3;
            y += r;
        }
        else if(c == 'L')
        {
            for(int j = 2*y-1; j>=2*(y-r); --j)
                if(arr[x*2][j] == 0)
                    arr[x*2][j] = 1;
                else if(arr[x*2][j] == 2)
                    arr[x*2][j] = 3;
            y -= r;
        }
        else if(c == 'U')
        {
            for(int j = 2*x+1; j <= 2*(x+r); ++j)
                if(arr[j][y*2] == 0)
                    arr[j][y*2] = 2;
                else if(arr[j][y*2] == 1)
                    arr[j][y*2] = 3;
            x += r;
        }
        else
        {
            for(int j = 2*x-1; j>= 2*(x-r); --j)
                if(arr[j][y*2] == 0)
                    arr[j][y*2] = 2;
                else if(arr[j][y*2] == 1)
                    arr[j][y*2] = 3;
            x -= r;
        }
        arr[x*2][y*2] = 3;
    }
}
 
int main()
{
    init();
    int ans = 10001;
    int y1, x1, y2, x2;
    for(int i = 0; i<101; ++i)
        for(int j = 0; j<101; ++j)
            if(arr[i*2][j*2] == 3)
            {
                int xp = -1, yp = -1;
 
                if(arr[i*2][j*2+1] == 1)
                    for(int k = 2*j+1; k<201; ++k)
                        if(arr[2*i][k] == 3)
                        {
                            yp = k/2-j;
                            break;
                        }
                if(arr[2*i+1][2*j] == 2)       
                    for(int k = 2*i+1; k < 201; ++k)
                        if(arr[k][2*j] == 3)
                        {
                            xp = k/2 - i;
                            break;
                        }
                if(xp == -1 || yp == -1)
                    continue;
                bool flag = true;
                for(int k = 2*j; k<=2*(j+yp); ++k)
                    if(arr[2*(i+xp)][k] == 0 || arr[2*(i+xp)][k] == 2)
                    {
                        flag = false;
                        break;
                    }
                for(int k = 2*i; k<=2*(i+xp); ++k)
                    if(arr[k][2*(j+yp)] == 0 || arr[k][2*(j+yp)] == 1)
                    {
                        flag = false;
                        break;
                    }
                if(!flag) continue;
                if(arr[2*(i+xp)][2*(j+yp)] == 3)
                    if(ans > xp*yp)
                    {
                        ans = xp*yp;
                        y1 = j;
                        x1 = i;
                        y2 = j+yp;
                        x2 = i+xp;
                    }
            }
    if(ans != 10001)
        cout << y1 << " " << x1 << "\n" << y2 << " " << x2;
    else
        cout << 0;
}
Colored by Color Scripter

cs

https://codeup.kr/problem.php?id=4458

단순 사각형

가장 작은 면적을 갖는 단순 사각형의 왼쪽 아래 꼭지점의 좌표를 첫째줄에, 오른쪽 위 꼭지점의 좌표를 둘째줄에 출력하면 된다. 좌표의 출력은 x좌표, y좌표 순으로 하며 하나의 빈칸을 사이에 둔다. 가장 작은 면적의 단순 사각형이 여러 개인 경우에는 그 중에서 하나만 출력하면 된다. 만일 단순 사각형이 존재하지 않으면 첫째줄에 0 을 출력한다.

codeup.kr

단순 사각형

KOI 1999 고등부 2번 문제입니다.

201*201 배열에 꼭지점들을 표시한다음, 해당 꼭지점을 좌상단 꼭지점으로 하는 사각형이 있는지 완전탐색으로 찾고, 넓이가 최소가 되는 사각형의 좌표를 출력했습니다.

(101*101 이 아닌 201*201을 한 이유는 (1,1), (1,2) 좌표에 꼭지점 표시가 되있더라도 101*101 좌표평면에선 두 점이 선으로 연결되있는지 아닌지 확인할 방법이 없기 때문에 201*201 좌표평면으로 표현했습니다.)

ABOUT ME

하루 코딩 하루 코딩

티스토리툴바