https://www.acmicpc.net/problem/5639


이진 검색 트리를 구현해주면 된다.


왼쪽 자식은 부모보다 작은 값이고, 오른쪽 자식은 부모보다 큰 값이다.


이진 검색 트리의 서브트리는, 마찬가지로 이진 검색 트리이다.



이 문제에서는 node 구조체를 root값 자체를 인덱스로 하도록 잡았다.


이전에 트리 순회 문제에서도 봤듯이, 순회가 문제에 섞일 때에는 인덱스를 루트의 값과 연결시켜서 잡아주는 것이 좋은 것 같다.



이 문제에서 주의할 사항은, 루트의 값 자체를 인덱스로 사용하기 때문에, 전체 노드의 개수가 아닌, root값의 허용 범위를


인덱스로 잡아줘야하다는 것이다.


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
#include<iostream>
using namespace std;
 
struct NODE{
    int l, r;
}n[1000002]; //인덱스가 root
//노드의 개수는 1000개인데, 인덱스를 루트로 쓰고 있기 때문에 루트의 허용 범위만큼 인덱스 필요
 
void postOrder(int rt) {
    if (rt == 0) return;
    postOrder(n[rt].l);
    postOrder(n[rt].r);
    cout << rt << '\n';
}
 
int main(void) {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int root;
    cin >> root; //전위순회니까 처음 나오는 게 무조건 tree의 root
    int num;
    while (cin >> num) {
        int cur = root;
        while (1) {
            if (num < cur) {
                if (n[cur].l != 0) cur = n[cur].l;
                else {
                    n[cur].l = num;
                    break;
                }
            }
            else {
                if (n[cur].r != 0) cur = n[cur].r;
                else {
                    n[cur].r = num;
                    break;
                }
            }
 
        }
    }
    postOrder(root);
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13

https://www.acmicpc.net/problem/6416


트리는


1. 간선의 개수 + 1 == 노드의 개수


2. 들어오는 간선이 없는 노드는 하나



1번 사실을 이용해서 node를 담는 set을 만들고, 간선의 개수를 카운트해서 개수 비교를 통해 풀었다.


추가적으로, 간선이 하나도 없어도 트리가 될 수 있다.


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
#include<iostream>
#include<unordered_set>
using namespace std;
unordered_set<int> nodes;
int main(void) {
 
    bool endFlag = false;
    int lineCnt = 0, caseCnt = 1;
    while (1) {
        int a, b;
        cin >> a >> b;
        if (a == -1 && b == -1) {
            endFlag = true;
            break;
        }
        if (a == 0 && b == 0) {
            if (lineCnt == 0 || nodes.size() == lineCnt + 1 ) {
                printf("Case %d is a tree.\n", caseCnt);
                caseCnt++;
                nodes.clear();
                lineCnt = 0;
                continue;
            }
            else{
                printf("Case %d is not a tree.\n", caseCnt);
                caseCnt++;
                nodes.clear();
                lineCnt = 0;
                continue;
            }
 
        }
        nodes.insert(a);
        nodes.insert(b);
        lineCnt++;
    }
 
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12

https://www.acmicpc.net/problem/2042


일반적인 구간합 구하기 문제라면, 배열을 별도로 두고 특정 인덱스까지 구간합을 저장해서 구하겠지만,


이 문제의 경우처럼 원소 자체가 빈번하게 업데이트 되면서 구간합을 구해야 한다면 인덱스 트리를 사용하는 게 편리하다.



인덱스 트리를 만드는 과정은 다음과 같다.


우선 leaf가 꽉 찬 트리로 만들어야 하기 때문에 원소의 개수보다 큰 가장 작은 2의 제곱수를 찾는다.


가령 예시의 경우처럼 원소가 5개라면 5보다 큰 가장 작은 2의 제곱수는 8이다.


기본적으로 배열은 1-indexed로 한다. 따라서 leaf에 처음 숫자들이 저장될 텐데, 인덱스 8부터 들어가면 된다.


비는 공간은 쿼리와 상관없는 수로 채워준다. (구간합 구하기 문제 같은 경우 0은 합에 영향을 미치지 않기 때문에 0으로 채워준다)


(가령 구간의 최댓값을 저장하는 인덱스 트리라면 구간의 최댓값에 영향을 미치지 않게 가장 작은 수로 비는 부분을 채워주면 된다)



인덱스를 찾았으니 구간합을 채워주면 된다.


부모의 인덱스는 자식 인덱스 /2, 왼쪽 자식은 부모 인덱스 *2, 오른쪽은 *2 +1 이라는 것을 이용해서 쿼리를 만들어주면 된다.


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
#include<iostream>
#define MAX 1000002
using namespace std;
 
typedef long long ll;
ll idxTree[4 * MAX];
 
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
 
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
 
int main(void) {
    int n, m, k;
    cin >> n >> m >> k;
    int start = 1;
    while (start < n) {
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
    }
    
    for (int i = 0; i < n; i++) { //원래 빈공간도 채워줘야 한다. 쿼리에 영향을 받지 않는 값으로
        cin >> idxTree[start + i];
    }
    //트리의 아래에서 위로 채워가기
    for (int i = start - 1; i >= 1; i--) {
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
    }
    for (int i = 0; i < m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c; //두 경우 모두 인덱스를 계산해서 넘겨야함, 차이는 새거-있던거
        if (a == 1) Update(b + start - 1, c - idxTree[b + start - 1]);
        else if (a == 2) cout << findSum(b + start - 1, c + start - 1) << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12
백준 1708 볼록 껍질 C++  (0) 2019.08.12

https://www.acmicpc.net/problem/1991


재귀로 트리 순회를 구현해주면 된다.


무조건 대문자로 들어온다고 했기 때문에 'A'를 빼주면서 A부터 0에 대응되도록 인덱스를 잡아준다.



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
#include<iostream>
using namespace std;
struct NODE {
    char left;
    char right;
}tree[27];
void preOrder(char root) {
    if (root == '.') return;
    cout << root;
    preOrder(tree[root-'A'].left);
    preOrder(tree[root-'A'].right);
}
void inOrder(char root) {
    if (root == '.') return;
    inOrder(tree[root - 'A'].left);
    cout << root;
    inOrder(tree[root - 'A'].right);
}
void postOrder(char root) {
    if (root == '.')return;
    postOrder(tree[root - 'A'].left);
    postOrder(tree[root - 'A'].right);
    cout << root;
}
int main(void) {
    int n;
    cin >> n;
    while (n--) {
        char parent, l, r;
        cin >> parent >> l >> r;
        tree[parent - 'A'].left = l;
        tree[parent - 'A'].right = r;
    }
    preOrder('A');
    cout << '\n';
    inOrder('A');
    cout << '\n';
    postOrder('A');
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12
백준 1708 볼록 껍질 C++  (0) 2019.08.12
백준 10255 교차점 C++  (0) 2019.08.11

https://www.acmicpc.net/problem/3878


이 문제도 볼록껍질 문제와 유사하다.


직선을 활용해서, 두 볼록껍질을 양분할 수 있는 지를 판단하는 문제이기 때문에, 예외 처리를 해줘야 한다.


한 볼록 껍질 도형에, 다른 볼록 껍질 도형이 들어가 있는 경우, 도형 교차 판별에서는 교차하지 않는다고 판단되기 때문에 추가적으로 처리 해줘야 한다.


이를 판단하는 방법은 다음과 같다.


특정 껍질을 감싸고 있는 큰 껍질(큰 볼록껍질)의 변들을 기준으로 작은 볼록 껍질의 점을 CCW하게 되면 모두 양수가 나온다.


이 때 외적은 교환 법칙이 성립하지 않기 때문에, CCW를 사용하는 순서와 방향이 중요하다.


반시계 방향으로 정렬해서 껍질을 만들었기 때문에, 검사도 반시계 방향으로 돌게 해주어야 한다.


따라서 스택에 있는 볼록 껍질을 이루는 점의 리스트를 벡터에 옮겨 올 때, 본래의 순서(반시계로 정렬된 순서)를 유지하면서 리스트에 들어갈 수 있게 정렬해줘야한다.


또한, CCW로 검사를 할 때에도, 점은 상관없지만 검사하는 선분은 반시게 방향으로 사용될 수 있도록 해야한다.



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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
struct POS {
    double x, y;
}b[101], w[101];
int B, W;
stack<int> stk;
vector<int> bHull, wHull;
int ccw(POS p1, POS p2, POS p3) {
    long double ret = (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - (p1.y*p2.x + p2.y*p3.x + p3.y * p1.x);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
long double distSquare(POS p1, POS p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmpB(POS p1, POS p2) {
    if (ccw(b[0], p1, p2) > 0) return true;
    else if (ccw(b[0], p1, p2) < 0) return false;
    else {
        long double dist1 = distSquare(b[0], p1);
        long double dist2 = distSquare(b[0], p2);
        if (dist1 < dist2) return true;
        else return false;
    }
}
bool cmpW(POS p1, POS p2) {
    if (ccw(w[0], p1, p2) > 0) return true;
    else if (ccw(w[0], p1, p2) < 0) return false;
    else {
        long double dist1 = distSquare(w[0], p1);
        long double dist2 = distSquare(w[0], p2);
        if (dist1 < dist2) return true;
        else return false;
    }
}
void grahamScan(POS p[],int num, int flag) {
    
    stk.push(0);
    if (num > 1) //정점이 2개 이상인 경우에만 
        stk.push(1);
    int next = 2;
    
 
    while (next < num) {
        while (stk.size() >= 2) {
            int sec = stk.top();
            stk.pop();
            int fir = stk.top();
            if (ccw(p[fir], p[sec], p[next]) > 0) {
                stk.push(sec);
                break;
            }
        }
        stk.push(next++);
    }
 
    if (flag == 0) {
        while (!stk.empty()) {
            bHull.push_back(stk.top());
            stk.pop();
        }
        sort(bHull.begin(), bHull.end()); //스택에 뒤집어져서 들어가 있으니까 순서를 맞춰서 넣어줌
        bHull.push_back(bHull[0]);
    }
    else {
        while (!stk.empty()) {
            wHull.push_back(stk.top());
            stk.pop();
        }
        sort(wHull.begin(), wHull.end());
        wHull.push_back(wHull[0]);
    }
}
bool isCross(POS p1, POS p2, POS p3, POS p4) {
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && 
        ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0) {
        
        if ((p1.x < p3.x && p1.x < p4.x && p2.x < p3.x && p2.x < p4.x) ||
            (p3.x < p1.x && p3.x < p2.x && p4.x < p1.x && p4.x < p2.x)) return false;
        if ((p1.y < p3.y && p1.y < p4.y && p2.y < p3.y && p2.y< p4.y) ||
            (p3.y < p1.y && p3.y < p2.y && p4.y < p1.y&& p4.y < p2.y)) return false;
        return true;
    }
    return false;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        bHull.clear();
        wHull.clear();
        cin >> B >> W;
        double bymin = 20000, wymin = 20000;
        int byminIdx = 0, wyminIdx = 0;
        for (int i = 0; i < B; i++) {
            cin >> b[i].x >> b[i].y;
            if (b[i].y < bymin) {
                bymin = b[i].y;
                byminIdx = i;
            }
            else if (b[i].y == bymin) {
                if (b[i].x < b[byminIdx].x) byminIdx = i;
            }
        }
        swap(b[0], b[byminIdx]);
        sort(b + 1, b + B, cmpB);
        grahamScan(b, B, 0); //역순으로 벡터 형성
        
        for (int i = 0; i < W; i++) {
            cin >> w[i].x >> w[i].y;
            if (w[i].y < wymin) {
                wymin = w[i].y;
                wyminIdx = i;
            }
            else if (w[i].y == wymin) {
                if (w[i].x < w[wyminIdx].x) wyminIdx = i;
            }
        }
        swap(w[0], w[wyminIdx]);
        sort(w + 1, w + W, cmpW);
        grahamScan(w, W, 1);
 
        //만나면 점 분리 할 수 없는 것
        
        bool meet = false;
 
        for (int i = 0; i < bHull.size()-1; i++) {
            for(int j = 0; j < wHull.size()-1; j++) {
                if (isCross(b[bHull[i]], b[bHull[i + 1]], w[wHull[j]], w[wHull[j + 1]])) {
                    meet = true;
                    break;
                }
            }
            if (meet) break;
        }
    
        if (meet) { //만나니까 분리할 수 없음
            cout << "NO" << '\n';
            continue;
        }
 
        //CCW가 모두 > 0 -> 하나가 나머지를 포함하는 것
        bool allPlus = true;
        for (int i = 0; i < bHull.size() - 1; i++) {
            for (int j = 0; j < wHull.size() - 1; j++) {
                if (ccw(b[bHull[i]], b[bHull[i + 1]], w[wHull[j]]) <= 0) {
                    allPlus = false;
                    break;
                }
            }
            if (!allPlus) 
                break;
        }
        if (allPlus) {
            cout << "NO\n";
            continue;
        }
 
        allPlus = true;
        for (int i = 0; i < wHull.size() - 1; i++) {
            for (int j = 0; j < bHull.size() - 1; j++) {
                if (ccw(w[wHull[i]], w[wHull[i + 1]], b[bHull[j]]) <= 0) {
                    allPlus = false;
                    break;
                }
            }
            if (!allPlus) break;
        }
        if (allPlus) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
    }
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 1708 볼록 껍질 C++  (0) 2019.08.12
백준 10255 교차점 C++  (0) 2019.08.11
백준 1485 정사각형 C++  (0) 2019.08.11

https://www.acmicpc.net/problem/1708


Graham scan을 활용해서 볼록껍질을 만들어주면 된다.


일단 확인 할 것은, 껍질의 변에 점이 여러 개 있는 경우에는 가장 바깥점만 취한다는 것이다.


또한 문제에서, x y 좌표 값이 정수라는 보장이 없기 때문에, 실수형으로 값을 처리해주면 되겠다.



Graham scan 알고리즘

1. y좌표가 가장 작은, y좌표가 가장 작은 값이 여러 개라면 그 중에서 x좌표가 가장 작은 점을 극값으로 잡는다.


2. 잡은 극값을 0번째 정점으로 옮기고, 극값을 기준으로 나머지 점들을 각도순으로 정렬한다.


2-1. 각도순으로 정렬할 때에는, 반시계 방향으로 정렬되도록 한다. 따라서 CCW가 양수가 되도록 정렬하되, CCW가 0이되는 두 점이 있다면, 더 가까운 점이 앞으로 올 수 있도록 정렬해준다.


2-2. 거리를 구할 때는 오차를 방지하기 위해, 루트를 씌우지 않는다. 어짜피 비교만 하면 되니까 상관 없다.


3. 전처리가 끝났다면, scan을 시작한다.

먼저 0번째와 1번째를 스택에 넣어준다. (알고리즘은 인덱스로만 진행한다)

next를 2로 선언한다.


참고로, 알고리즘을 이해할 때는 항상 second 값이 껍질에 포함될 수 있는 유효한 점인지를 판단한다고 생각하고 흐름을 따라가면 이해가 쉽다.


스택에서 두개를 꺼내서 next와 CCW를 해본다. 반시계 방향으로 돈다면(CCW가 양수라면) second를 first로 바꾸고 next를 second로 바꾸고 다음을 확인한다. 이때 제대로 되지 않았다는 것은, 현재의 second가 된 이전의 next가 포함되면 안된다는 것이다. next는 다음 요소로 바꾸고, first와 second는 이전의 것들로 바꿔준다. 


next가 마지막 점이 될 때 까지 이걸 쭉 반복한다.



알고리즘은 이렇게 끝난다. 끝나고 나면 스택의 가장 하단부터 가장 상단까지, 순서대로 볼록 껍질을 형성하는 점의 인덱스가 들어있을 것이다.


이 문제에서는 이 점들의 개수만 파악하면 되기 때문에 스택의 크기만 확인하면 되지만, 이 점들의 목록이 순서대로 필요할 때에는 pop하면서 벡터에 넣어어주고, 이후에 정렬해줘야한다.


그리고, 이 점들을 선으로 연결해서 도형을 만든 이후에 어떤 선분과 볼록 껍질의 교차여부를 판단한다든지 할 때에는, 마지막 점과 첫점을 반드시 연결해줘야 한다.


가령 1,2,3,4,5를 그대로 연결하면 5와 1은 끊어져 있는 상태이다. 이를 연결시켜줘야 한다는 의미이다. 연결은 간단하게 6번째 인덱스에 1을 넣어주면 된다.


[수정] 위에 있는 코드가 chain 만드는 과정을 좀 더 간결하게 표현한 코드이다.


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
//극값 찾기 -> 각도 정렬 -> graham scan(스택대신 벡터사용)
//동일 선분 위에 점이 여러개 존재하는 경우 어떻게 하는지 문제에서 확인
// ->양 끝 점만 개수에 포함 (스캔할 때 ccw 0이하까지 pop)
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
struct POS {
    double x, y;
}b[100002], p;
int n;
 
int ccw(POS p1, POS p2, POS p3) {
    long double temp = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
    if (temp < 0) return -1;
    else if (temp > 0) return 1;
    else return 0;
}
long double distSquare(POS p1, POS p2) {
    long double d1 = (p1.x - p2.x) * (p1.x - p2.x);
    long double d2 = (p1.y - p2.y) * (p1.y - p2.y);
    return d1 + d2;
}
bool cmp(POS a, POS b) {
    if (ccw(p, a, b) > 0) return true;
    else if (ccw(p, a, b) < 0) return false;
    else {
        if (distSquare(p, a) < distSquare(p, b)) return true;
        else return false;
    }
}
 
 
int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> b[i].x >> b[i].y;
    
    p = b[0]; //극값
    //극값 검색
    for (int i = 1; i < n; i++) {
        if (b[i].x < p.x) p = b[i];
        else if (b[i].x == p.x) {
            if (b[i].y < p.y) p = b[i];
        }
    }
    
    sort(b, b + n, cmp); //각도 정렬
 
    vector<POS> s;
    
    for (int i = 0; i < n; i++) {
        while (s.size() >= 2 && ccw(s[s.size()-2], s[s.size()-1], b[i]) <= 0) {
            s.pop_back();
        }
        s.push_back(b[i]);
    }
    
    /*for (int i = 0; i < s.size(); i++)
        printf("%lf %lf\n", s[i].x, s[i].y);*/
    cout << s.size() << '\n';
}
cs







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
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
 
struct POS {
    double x, y;
}p[100001];
 
int n, yminIdx = 0;
double yMin = 50000;
stack<int> stk;
 
int ccw(POS p1, POS p2, POS p3) {
    long double ret = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
 
long double dist(POS p1, POS p2) { //거리 제곱 반환
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
 
bool cmp(POS a, POS b) { //극값 기준 반시계 방향 정렬 + 극값과 거리 가까운 게 앞
    if (ccw(p[0], a, b) > 0) return true;
    else if (ccw(p[0], a, b) < 0) return false;
    else {
        long long distA = dist(p[0], a);
        long long distB = dist(p[0], b);
        if (distA < distB) return true;
        else
            return false;
    }
}
void grahamScan() {
    stk.push(0);
    stk.push(1);
    int next = 2;
    while (next < n) {
        while (stk.size() >= 2) {
            int sec = stk.top();
            stk.pop();
            int fir = stk.top();
            //printf("%d %d %d %d\n", fir, sec, next, ccw(p[fir], p[sec], p[next]));
            if (ccw(p[fir], p[sec], p[next]) > 0) {
                stk.push(sec);
                break;
            }
        }
        stk.push(next++);
    }
}
//bool cmp1(POS a, POS b) { //극값 찾을 때 sort 활용하는 경우
//    if (a.x <b.x) return true;
//    else if (a.x > b.x) return false;
//    else {
//        if (a.y < b.y) return true;
//        else
//            return false;
//    }
//}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    //기준점은 y값, x값이 최소인 곳
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
        if (p[i].y < yMin) {
            yMin = p[i].y;
            yminIdx = i;
        }
        else if (p[i].y == yMin)
            if (p[i].x < p[yminIdx].x) yminIdx = i;
    }
    
    swap(p[0], p[yminIdx]); //기준점을 0번째 점으로
 
    //sort(p, p + n, cmp1); //정렬해서 극값 찾는것보다 입력 받으면서 극값 찾는게 빠름
 
    sort(p+1, p + n, cmp); //각도 정렬
 
    grahamScan();
    cout << stk.size() << '\n';
    /*while (!stk.empty()) {
        cout << stk.top() << ' ';
        stk.pop();
    }*/
    return 0;
}
 
cs




저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12
백준 10255 교차점 C++  (0) 2019.08.11
백준 1485 정사각형 C++  (0) 2019.08.11
백준 6439 교차 C++  (0) 2019.08.11

https://www.acmicpc.net/problem/10255


케이스 처리를 어떤 순서로 하는지가 중요하고, 예외 처리를 꼼꼼하게 하는 것이 중요한 문제이다.


기본적으로, 교점이 존재하지 않을 때를 먼저 없애준다. 교점이 없으면 나머지 모든 케이스를 볼 필요가 없으니까.


비슷한 맥락으로 다음으로 교점이 무수히 많은 경우를 처리해준다.


그리고 경우를 나눠서, 선분이 사각형의 꼭지점을 지나는 경우와 그렇지 않은 경우로 나눠서 진행한다.



1. 교점이 없는지 판단하는 것은, 기본적인 예외처리가 포함된 템플릿을 활용한다. CCW 곱을 연산한 결과가 모두 0보다 작거나 같고, 사각형의 내부에 선분이 존재하지 않는다면 만난다고 판단한다.


한 번이라도 만나게 되면 교점이 존재한다고 판단하고 스킵하면 된다.


2. 교점이 무수히 많은지 판단은, 직관적으로 하드코딩 했다. 기본적인 정렬은 x좌표가 작은 점이 선분의 시작점으로 오게 했다. 하지만 y좌표에 대해서는 정렬을 하지 않았기 때문에 (당연히 x좌표 혹은 y좌표 둘 중 하나로 밖에 정렬할 수 없다) y좌표는 어떤 크기 관계를 가지는지 알 수 없다.


따라서 직사각형의 각 변위에 그대로 선분이 놓이는 경우를 모두 따져주면 된다.


3. 선분이 사각형의 꼭짓점을 지나는 경우

이런 상황이면, 선분의 두 점을 A,B 그리고 사각형의 두 점을 C, D라고 했을때, 선분이 C를 지나간다면 CCW(A,B,C) = 0 일 것이고, 선분이 D를 지난다면 CCW(A,B,D) = 0 일 것이다.


즉 선분이 사각형의 꼭짓점을 지나는 경우는, 선분을 기준으로 사각형의 변을 CCW 했을 때 무조건 0이 나오게 된다.

따라서 함수를 구현할 때, CCW(A,B,C) * CCW(A,B,D) == 0 and CCW(C,D,A) * CCW(C,D,B) <= 0  이를 만족하면 선분 AB가 꼭짓점 C혹은 D를 지나는 경우이다. 이 때 카운트를 하게 되면, CD 인 경우와 선분 EC인 경우에도 중복으로 카운트가 될 것이기 때문에 (C를 AB가 지난다고 할 경우) 최종 카운트 횟수를 2로 나눠준다.


4. 선분이 사각형의 변을 지나는 경우

CCW(A,B,C) & CCW(A,B,D) < 0 and CCW(C,D,A) * CCW(C,D,B) <= 0 이 상황이다. 앞의 부등식이 0이게 되면 위에서 봤듯이 꼭짓점을 지나는 경우이다.


추가적으로 사각형의 변을 기준으로 하는 CCW가 그대로 <= 이어도 괜찮은 이유는, 가령 사각형의 변 CD위에 선분 AB의 끝점 A가 위치해 있는 경우 CCW(C,D,A)가 0이 된다. 이 경우는 특별한 경우가 아니고 그냥 CD와 AB가 한 점에서 만난다는 조건일 뿐이다. 따라서 고려해 줄 필요가 없다. 0이 들어가고 안 들어가고를 신경쓸 필요도 없고 말이다.


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
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct POS {
    int x, y;
};
vector<int> ans;
set<pair<int, int> > chk;
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    ll ret = (x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1);
    if (ret > 0) return 1;
    else if (ret < 0) return -1;
    else 
        return 0; 
}
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    //ccw곱 음수 + 사각형 내부 피하면 교차
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        if ((x1 < x3 && x1 < x4 && x2 < x3 && x2 < x4) ||
            (x3 < x1 && x3 < x2 && x4 < x1 && x4 < x2)) return false;
        if ((y1 < y3 && y1 < y4 && y2 < y3 && y2 < y4) ||
            (y3 < y1 && y3 < y2 && y4 < y1 && y4 < y2)) return false;
        return true;
    }
    return false;
}
bool isCross_rect_point(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    int line = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
    int rect = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
    if (line == 0 && rect <= 0) return true;
    else return false;
}
bool isCross_rect_line(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    int line = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
    int rect = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
    if (line < 0 && rect <= 0) return true;
    else return false;
}
 
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        int xmin, ymin, xmax, ymax;
        cin >> xmin >> ymin >> xmax >> ymax;
        POS r1 = { xmin, ymin };
        POS r2 = { xmin, ymax };
        POS r3 = { xmax, ymin };
        POS r4 = { xmax, ymax };
 
        POS l1, l2;
        int x1, y1, x2, y2;
        cin >> l1.x >> l1.y >> l2.x >> l2.y;
        if (l1.x > l2.x) swap(l1, l2);
 
        //1. 교점 없음
        bool isNone = true;
        if (isCross(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y)|| 
         isCross(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y)||
         isCross(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y)|| 
         isCross(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) isNone = false;
        if (isNone) {
            cout << 0 << '\n';
            continue;
        }
 
        //2. 교점 무한 -> 좌표 기준으로만 정렬해서, y는 뭐가큰지 모르니까 두 경우 다 고려
        if (l1.x == l2.x && l1.x == xmin) {
            if ((l1.y < ymax) && (l2.y > ymin) || (l2.y < ymax) && (l1.y > ymin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        else if (l1.x == l2.x && l1.x == xmax) {
            if ((l1.y < ymax) && (l2.y > ymin) || (l2.y < ymax) && (l1.y > ymin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        else if (l1.y == l2.y && l1.y == ymax) {
            if ((l1.x < xmax) && (l2.x > xmin)|| (l2.x < xmax) && (l1.x > xmin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        else if (l1.y == l2.y && l1.y == ymin) {
            if ((l1.x < xmax) && (l2.x > xmin)|| (l2.x < xmax) && (l1.x > xmin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        
        int cnt_rect_line = 0, cnt_rect_point = 0;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y)) cnt_rect_line++;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y)) cnt_rect_line++;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y)) cnt_rect_line++;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) cnt_rect_line++;
 
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y)) cnt_rect_point++;
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y)) cnt_rect_point++;
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y)) cnt_rect_point++;
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) cnt_rect_point++;
 
        cout << cnt_rect_line + cnt_rect_point/2 << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 3878 점 분리 C++  (0) 2019.08.12
백준 1708 볼록 껍질 C++  (0) 2019.08.12
백준 1485 정사각형 C++  (0) 2019.08.11
백준 6439 교차 C++  (0) 2019.08.11
백준 2162: 선분 그룹 C++  (0) 2019.08.11

https://www.acmicpc.net/problem/1485


네 점이 주어질 때 정사각형인지 판별하면 된다.


네 점이 어떤 순으로 정렬되어서 들어온다는 보장이 없기 때문에, 사용하기 편하게 정렬을 해줘야 한다.


본인은 x좌표 오름차순으로 우선 정렬하고, x좌표가 같은 경우에 y좌표 오름차순으로 정렬했다.


따라서


p2    p3



p0    p1


이런식으로 정렬되게 된다. 이후에는 거리를 구해줘야 하는데, 거리를 구할 때 동일한지 여부만 비교하면 되기 때문에, 오차 방지를 위해서


루트를 씌우지 않고 거리를 구했다. 즉 거리의 제곱을 활용해서 거리 비교를 했다.


거리의 제곱이 같아도, 거리는 같은 것이기 때문이다.


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
#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
struct PT {
    int x, y;
};
PT p[4];
int dis[4][4];
bool cmp(PT a, PT b) { //x좌표 기준 오름차순. x좌표 같으면 y좌표 오름차순
    if (a.x < b.x) return true;
    else if (a.x == b.x) {
        if (a.y < b.y) return true;
        else return false;
    }
    else
        return false;
}
ll distSquare(PT a, PT b) { //오차 방지를 위해 루트 생략(비교만 하면 되니까)
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
int main(void) {
    int n;
    cin >> n;
    while (n--) {
        
        for (int i = 0; i < 4; i++) {
            cin >> p[i].x >> p[i].y;
        }
        sort(p, p + 4, cmp);
        
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (i == j) continue; //같으면 거리 0
                dis[i][j] = distSquare(p[i], p[j]);
            }
        }
        if (dis[0][1] == dis[0][2] && dis[3][2] == dis[3][1] &&
            dis[0][3] == dis[1][2]) //네변 길이 같고, 대각선 길이 같으면
            cout << 1 << '\n';
        else
            cout << 0 << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1708 볼록 껍질 C++  (0) 2019.08.12
백준 10255 교차점 C++  (0) 2019.08.11
백준 6439 교차 C++  (0) 2019.08.11
백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10

https://www.acmicpc.net/problem/6439



사각형과 선분의 교차 여부를 판단해주면 된다.


사각형 정점의 입력이 두 점이 주어지는데, 위치가 정해져있지 않다. x, y좌표들을 적절하게 대소비교해서 정점 네개를 잡아서


사각형을 만들어줘야 한다.



한 점만 공유해도 교차하는 것으로 간주한다고 했기 때문에, ccw 결과에 0을 포함시켜도 좋다.


사각형의 네 변과 선분을 각각 교차판정 해주고, 사각형의 내부에 선분이 존재하는지 확인한다.



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
#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
struct PT {
    ll x, y;
};
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    ll ret = (x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0; //일직선 상에 위치
}
 
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        //아예 멀리 떨어져 있는 경우
        if ((x1 < x3 && x1 < x4 && x2 < x3 && x2 < x4) ||
            (x3 < x1 && x3 < x2 && x4 < x1 && x4 < x2)) return false;
        if ((y1 < y3 && y1 < y4 && y2 < y3 && y2 < y4) ||
            (y3 < y1 && y3 < y2 && y4 < y1 && y4 < y2)) return false;
        return true;
    }
    return false;
}
 
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        PT l1, l2, r1, r2, r3, r4;
        cin >> l1.x >> l1.y >> l2.x >> l2.y;
        ll tmpx1, tmpx2, tmpy1, tmpy2;
        cin >> tmpx1 >> tmpy1 >> tmpx2 >> tmpy2; //사각형 좌표는 의미없는 순서로 들어옴
 
        r1 = { min(tmpx1, tmpx2), min(tmpy1, tmpy2) }; 
        r2 = { min(tmpx1, tmpx2), max(tmpy1, tmpy2) };
        r3 = { max(tmpx1, tmpx2), min(tmpy1, tmpy2) };
        r4 = { max(tmpx1, tmpx2), max(tmpy1, tmpy2) };
 
        if (isCross(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y) ||
            isCross(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y) ||
            isCross(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y) ||
            isCross(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) {
            cout << "T" << '\n'; //하나라도 교차하면
        }
        else {
            //내부에 있거나 안만나거나 (isCross false)
            if ((r1.x < l1.x && r1.x < l2.x && l1.x < r3.x && l2.x < r3.x) &&
                (r1.y < l1.y && r1.y < l2.y && l1.y < r4.y && l2.y < r4.y)) {
                cout << "T" << '\n'; //사각형의 내부에 선분이 존재해서 만나지 않은 경우
            }
            else
                cout << "F" << '\n';
        }
    }
    return 0;
}
cs




복습



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
//좌표값 -> 정수이면서 크기 조건이 없음
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
};
 
ll ccw(POT p1, POT p2) {
    ll ret = p1.x*p2.y - p1.y*p2.x;
    if (ret == 0) return 0;
    else if (ret > 0) return 1;
    else return -1;
}
 
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
bool isCross(POT p1, POT p2, POT p3, POT p4) {
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
        ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0) {
        if ((p1.x < p3.x && p1.x < p4.x && p2.x < p3.x && p2.x < p4.x) ||
            (p3.x < p1.x && p3.x < p2.x && p4.x < p1.x && p4.x < p2.x)) return false;
        if ((p1.y < p3.y && p1.y < p4.y && p2.y < p3.y && p2.y < p4.y) ||
            (p3.y < p1.y && p3.y < p2.y && p4.y < p1.y && p4.y < p2.y)) return false;
        else
            return true;
    }    
    return false; //둘다 0이하 아니면 안 만남
}
 
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        POT st, en;
        cin >> st.x >> st.y >> en.x >> en.y;
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ll xmin, xmax, ymin, ymax;
        xmin = min(x1, x2);
        ymin = min(y1, y2);
        xmax = max(x1, x2);
        ymax = max(y1, y2);
        
        POT p[5];
        p[0] = { xmin, ymin };
        p[1] = { xmax, ymin };
        p[2] = { xmax, ymax };
        p[3] = { xmin, ymax };
        p[4] = p[0];
 
        //1. 교차하면 T
        bool endFlag = false;
        for (int i = 0; i < 4; i++)
            if (isCross(st, en, p[i], p[i + 1])) {
                cout << "T" << '\n';
                endFlag = true;
                break;
            }
        if (endFlag) continue;
 
        //2. 교차하지 않았으나, 사각형 내부에 선분이 존재하면 T
        if ((xmin < st.x && xmin < en.x && st.x < xmax && en.x < xmax) &&
            (ymin < st.y && ymin < en.y && st.y < ymax && en.y < ymax)) {
            cout << "T" << '\n';
            continue;
        }
        
        //3. 나머지
        cout << "F\n";
    }
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 10255 교차점 C++  (0) 2019.08.11
백준 1485 정사각형 C++  (0) 2019.08.11
백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10

https://www.acmicpc.net/problem/2162



n개의 선분들이 각각 두 개의 좌표로 표현되어서 주어진다.


이 각각의 선분이 교차하는 경우에 같은 그룹으로 본다고 했을 때, 그룹의 수와 가장 멤버수가 많은 그룹에 속한 선분의 개수는?



[알고리즘]


1. 입력으로 들어오는 모든 선분들에 대해서 교차판별을 진행한다.


2. union-find를 활용해서, 교차한다면 같은 그룹으로 root를 묶어준다.


3. root인 선분의 개수를 파악한다. (root의 개수가 곧 그룹의 개수)


4. 그룹을 이루는 선분의 수가 가장 많은 그룹의 선분의 수를 파악한다.



[풀이]


교차 판별은 CCW를 활용한다. 1. 선분 A에 대해서 B의 각 점과 CCW를 돌리고, 2. 선분 B에 대해서 A의 각 점과 CCW를 돌린다.


1과 2의 결과가 모두 음수여야 기본적으로 교차할 수 있는 각도로 주어져있는 상태이다.


추가적으로 문제에서 관통하지 않고 딱 만나기만 해도 교차로 간주한다고 했으므로 위 조건에 0이 되는 경우까지 추가해야 한다.



이제 놓여있는 상태에 따라서 만날 수도 있고 아닐 수도 있다.


선분 A를 이루는 두 점의 x좌표가 선분 B를 이루는 두 점의 X좌표 모두보다 작다면 당연히 만날 수 없다. y좌표의 경우도 마찬가지.


그리고 선분 B에 대해서도 마찬가지이다. 이럴 경우에는 위의 CCW결과의 곱이 둘 다 음수로 나오더라도 만날 수 없는 경우이다.



이를 진행할 때, 만난다고 판단되는 경우 union작업을 해줘야 한다. union-find를 진행하기 위해, 부모 배열(r[])을 모두 자기 자신으로 초기화 해준다.


그리고 만난다고 판단되는 경우 union해준다.


이 작업을 마쳤다 하더라도, 모든 노드의 r[] 값이 최상위 부모로 갱신되었다는 보장이 없다. 따라서 getParent를 모든 지점에 대해 수행하여 r[] 값을 최상위 부모로 갱신해준다.


cnt[] 배열은 인덱스를 최상위 부모로 하는 선분의 수이다. cnt[1] = 3이라면, 1을 최상위 부모로하는 노드가 3개 있다는 것이다.


따라서 cnt[] 값이 0초과인 경우를 카운트 해주면, 그룹의 수를 셀 수 있다.


cnt[] 값이 최대인 곳이 최대 크기의 그룹일 것이다.



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
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
struct LINE {
    int x1, y1, x2, y2;
 
};
LINE L[3001];
 
int r[3001]; // index의 root를 저장
int cnt[3001]; //index를 root로 하는 그룹 구성원 수
 
int getParent(int a) {
    if (r[a] == a) return a;
    else
        return r[a] = getParent(r[a]); //갱신하면서 찾으러 올라가야함
}
 
void join(int a, int b) {
    r[getParent(a)] = getParent(b);
}
 
ll ccw(int x1, int y1, int x2, int y2, int x3, int y3) { 
    ll ret = (x1*y2 + x2*y3 +x3*y1) - (y1*x2 + y2*x3 + y3*x1);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
 
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    //만나면 true, 아니면 false -> 선분 ccw 곱의 결과가 음수이지만 안 만나는 경우
    //예외 처리 필요 -> 0인 경우도 예외 처리에 포함시켜야함(평행이동 하면 관통안하고 만나기만하는 경우)
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        //여기까지 보면 각도 상으로는 만날 수 있는 조건을 갖춤
        if ((x1 > x3 && x1 > x4 && x2 > x3 && x2 > x4) ||
            (x3 > x1 && x3 > x2 && x4 > x1 && x4 > x2)) return false;
        else if ((y1 > y3 && y1 > y4 && y2 > y3 && y2 > y4) ||
            (y3 > y1 && y3 > y2 && y4 > y1 && y4 > y2)) return false;
        else
            return true;
    }
    return false; //애초에 양수면 교차X
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) //유니온 파인드 할 때 편하라고 1-indexed
        cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
    
    for (int i = 1; i <= n; i++) r[i] = i; //root 자기 자신으로 초기화
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (isCross(L[i].x1, L[i].y1, L[i].x2, L[i].y2, L[j].x1, L[j].y1, L[j].x2, L[j].y2))
                join(i, j);
        }
    }
    //여기까지 join해도, r[]이 최상위 부모노드를 가지지 않음. 따라서 추가 순회하면서 카운트
    for (int i = 1; i <= n; i++)
        cnt[getParent(i)]++;
    /* 부모 최신화와, 카운팅 분리
    for (int i = 1; i <= n; i++)
        int tmp = getParent(i);
    
    for (int i = 1; i <= n; i++)
        cnt[r[i]]++;
        */
    
    int groupCnt = 0, maxCnt = 0;
    for (int i = 1; i <= n; i++) {
        //cnt[]가 0이 아닌 곳이 그룹인 곳
        if (cnt[i] > 0) groupCnt++;
 
        if (cnt[i] > maxCnt) 
            maxCnt = cnt[i];    
    }
    cout << groupCnt << '\n' << maxCnt;
    return 0;
}
cs





복습


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
//좌표값 정수
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
};
 
struct LINE {
    POT st, en;
}l[3001];
 
int n, r[3001], cnt[3001];
ll ccw(POT p1, POT p2) {
    ll ret = p1.x*p2.y - p1.y*p2.x;
    if (ret == 0) return 0;
    else if (ret > 0) return 1;
    else return -1;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
int getPar(int a) {
    if (r[a] == a) return a;
    else
        return r[a] = getPar(r[a]);
}
void join(int a, int b) {
    a = getPar(a);
    b = getPar(b);
    if (a < b) 
        r[b] = a;
    
    else 
        r[a] = b;
    
}
bool isCross(LINE l1, LINE l2) {
    if (ccw(l1.st, l1.en, l2.st) * ccw(l1.st, l1.en, l2.en) <= 0 &&
        ccw(l2.st, l2.en, l1.st) * ccw(l2.st, l2.en, l1.en) <= 0) {
        if ((l1.st.x < l2.st.x && l1.st.x < l2.en.x && l1.en.x < l2.st.x&&l1.en.x < l2.en.x) ||
            (l2.st.x < l1.st.x && l2.st.x < l1.en.x && l2.en.x < l1.st.x&&l2.en.x < l1.en.x)) return false;
        if ((l1.st.y < l2.st.y && l1.st.y < l2.en.y && l1.en.y < l2.st.y&&l1.en.y < l2.en.y) ||
            (l2.st.y < l1.st.y && l2.st.y < l1.en.y && l2.en.y < l1.st.y&&l2.en.y < l1.en.y)) return false;
        return true;
    }
    return false; //안 만남
}
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> l[i].st.x >> l[i].st.y >> l[i].en.x >> l[i].en.y;
    
    for (int i = 0; i < n; i++) 
        r[i] = i; //자기 자신으로 최상위 부모 초기화
    
 
    //겹치면 union
    for (int i = 0; i < n; i++) 
        for (int j = i+1; j < n; j++) {
            if (isCross(l[i], l[j])) {
                join(i, j);
            }
        }
    
    for (int i = 0; i < n; i++)
        cnt[getPar(i)]++;
 
    int mx = -1, ct = 0;
    for (int i = 0; i < n; i++) {
        if (mx < cnt[i]) 
            mx = cnt[i];
        if (cnt[i] > 0) ct++;
    }
    printf("%d\n%d", ct, mx);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1485 정사각형 C++  (0) 2019.08.11
백준 6439 교차 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10

+ Recent posts

티스토리툴바