반응형

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

 

17386번: 선분 교차 1

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 선분에 대해 ccw를 구하고 각 선분의 ccw를 곱한 값이 모두 0보다 작으면 선분은 교차합니다.

 

2. 그렇지 않다면 교차하지 않는 선분입니다.

 

[ 소스코드 ]

 

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
#include<iostream>
#define ll long long
 
using namespace std;
 
pair<ll, ll> arr[4];
 
int ccw(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
    ll ret = (a.first * b.second + b.first * c.second + c.first * a.second) - (b.first * a.second + c.first * b.second + a.first * c.second);
 
    if (ret > 0) return 1;
    else return -1;
}
 
int main()
{
    for (int i = 0; i < 4; i++) {
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
    }
 
    if (ccw(arr[0], arr[1], arr[2]) * ccw(arr[0], arr[1], arr[3]) < 0 && ccw(arr[2], arr[3], arr[0]) * ccw(arr[2], arr[3], arr[1]) < 0) {
        printf("%d", 1);
    }
    else {
        printf("%d", 0);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22
[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
[ 백준 ] 3584번 - 가장 가까운 공통 조상 (C++)  (0) 2022.11.18
반응형

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

 

2162번: 선분 그룹

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/5

 

[ 백준 ] 17387번 - 선분 교차 2 (C++)

https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net [ 문제풀이 ] 선분이 교차할..

rudalsd.tistory.com

 

위 문제를 풀어보고 오는 것을 추천드립니다!

 

이 문제는 선분 교차 2 문제에서 Union - Find를 추가한 문제입니다. 직선의 개수가 3000개밖에 되지 않으므로 2중 for문을 돌려도 큰 문제가 없으므로 2중 for문으로 문제를 풀었습니다. 선분이 교차한다면 Union을 해주고 마지막에 모든 선분을 돌면서 Find를 통해 map에 부모 노드를 저장해줍니다.

 

그리고 map.size()와 map[ i ]의 값 중 제일 큰 값을 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <algorithm>
#include<unordered_map>
 
using namespace std;
 
struct pos {
    int x;
    int y;
};
 
pos arr[6000];
int vect[3001];
unordered_map<int, int> m;
 
int N;
 
int Find(int n)
{
    if (vect[n] == n) return n;
    return vect[n] = Find(vect[n]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    if (pa != pb) {
        vect[pb] = pa;
    }
}
 
bool cmp(pos left, pos right)
{
    if (left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    int cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N * 2; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    for (int i = 0; i < N ; i++) {
        sort(arr + i * 2, arr + (i + 1) * 2, cmp);
    }
 
    for (int i = 0; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int l1 = closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2]) * closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2 + 1]);
            int l2 = closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2]) * closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2 + 1]);
            if (l1 == 0 && l2 == 0) {            //두 선이 일직선상에 있을 때
                if (cmp(arr[j*2], arr[i*2+1]) && cmp(arr[i*2], arr[j*2+1])) {
                    if (Find(i) != Find(j)) {
                        Union(i, j);
                    }
                }
            }
            else if (l1 <= 0 && l2 <= 0) {
                if (Find(i) != Find(j)) {
                    Union(i, j);
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        m[Find(i)]++;        //집합에 속해있다면 선분을 map에 추가
    }
 
    int ans = 0;
 
    for (auto it = m.begin(); it != m.end(); it++) {
        if (ans < it->second) {    //집합 중 가장 큰 집합을 ans에 대입
            ans = it->second;
        }
    }
 
    cout << m.size() << endl << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
반응형

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

 

17387번: 선분 교차 2

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

www.acmicpc.net

 

[ 문제풀이 ]

 

선분이 교차할 때의 조건을 알아야 풀 수 있는 문제입니다.

 

 

위와 같이 2개의 선분을 서로 교차한다고 말합니다. 이때 p1과 p2를 이은 선분을 벡터 v1이라고 하면 v1 = p2 - p1이 됩니다. 이와 같은 원리로 v2 = p3 - p1, v3 = p4 - p1이라고 하면 다음과 같이 나타낼 수 있습니다.

 

 

이때 v1과 v2를 외적 하면 반시계 방향이므로 양수가 나오고, 반대로 v1과 v3를 외적 하면 시계방향이므로 음수가 나옵니다. 위 결과로 보아 벡터들의 외적 값을 구하고 그 방향이 반대라면 선분이 교차한다고 표현할 수 있습니다.

 

 

하지만 위와 같은 상황에서는 조건을 만족하지만 교차한다고 표현할 수 없습니다.

 

이 때에는 또 다른 벡터를 이용해서 구해줍니다. 즉, v4 = p4 - p3, v5 = p2 - p3, v6 = p1 = p3일 때 v4를 기준으로 모두 같은 방향에 있기 때문에 조건을 만족하지 않습니다.

 

 

따라서 ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0이 되어야 합니다.

 

다른 예외 사항도 몇 가지가 있습니다.

 

3개의 점이 한 직선상에 있거나 4개의 점이 한 직선상에 있는 경우입니다.

 

 

위와 같은 경우 p1, p2, p3가 같은 직선상에 있고, ccw(p1, p2, p3)는 0이 나오게 됩니다.

 

즉, ccw(p1, p2, p3) * ccw(p1, p2, p4) == 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0 이거나,

ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) == 0을

 

 

마지막으로 위와 같은 상황에서는 모든 ccw가 0이므로 다른 조건으로 교차 여부를 판단해야 합니다. 한 직선을 기준으로 p1 < p2와 p3 < p4를 만족한다면 p2 > p3와 p4 > 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
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
 
using namespace std;
 
struct pos {
    long long x;
    long long y;
};
 
pos arr[4];
 
bool cmp(pos left, pos right)
{
    if(left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    long long cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    for (int i = 0; i < 4; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    sort(arr, arr + 2, cmp);
    sort(arr + 2, arr + 4, cmp);
    int l1 = closs(arr[0], arr[1], arr[2]) * closs(arr[0], arr[1],arr[3]);
    int l2 = closs(arr[2], arr[3], arr[0]) * closs(arr[2], arr[3], arr[1]);
    if (l1 == 0 &&l2 == 0) {            //두 선이 일직선상에 있을 때
        if (cmp(arr[2], arr[1]) && cmp(arr[0], arr[3])) {
            cout << 1;
            return 0;
        }
    }
    else if (l1 <= 0 && l2 <= 0) {
        cout << 1;
        return 0;
    }
 
    cout << 0;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21

+ Recent posts

티스토리툴바