반응형

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

 

10216번: Count Circle Groups

백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 진영의 위치와 R을 입력받아 arr에 저장하고, visited 배열을 만들어 각 진영의 방문 여부를 체크해 줍니다.

 

2. for문을 통해 모든 진영을 돌면서 visited[ i ] 가 0이라면 ans++를 해주고 bfs를 돌며 이어진 진영의 visited를 1로 갱신해 줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int x, y, R;
};
 
int T, N;
node arr[3000];
int visited[3000];
 
void bfs(int num)
{
    queue<int> q;
 
    q.push(num);
 
    while (!q.empty()) {
        const int x = arr[q.front()].x;
        const int y = arr[q.front()].y;
        const int R = arr[q.front()].R;
        q.pop();
 
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                const int xx = arr[i].x;
                const int yy = arr[i].y;
                const int RR = arr[i].R;
 
                if (sqrt(pow(x - xx, 2+ pow(y - yy, 2)) <= R + RR) {
                    visited[i] = 1;
                    q.push(i);
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N;
 
        for (int i = 0; i < N; i++) {
            int x, y, R;
            cin >> x >> y >> R;
            arr[i] = { x,y,R };
        }
 
        int ans = 0;
        fill(visited, visited + N, 0);
 
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                bfs(i);
                ans++;
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
반응형

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 > 0return 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
반응형
반응형

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

 

11758번: CCW

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 먼저 P1에서 P2로 향하는 벡터와 P1에서 P3로 향하는 벡터를 구합니다.

 

2.  두 벡터를 외적 합니다.

 

3. 외적의 값이 0보다 작다면 시계방향, 0보다 크다면 반시계 방향, 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
#include<iostream>
 
using namespace std;
 
pair<intint> P[3];
pair<intint> vect[2];
 
int main()
{
    for (int i = 0; i < 3; i++) {
        int x, y;
        scanf("%d %d"&x, &y);
 
        P[i] = { x,y };
    }
 
    vect[0= { P[0].first - P[1].first, P[0].second - P[1].second };
    vect[1= { P[0].first - P[2].first, P[0].second - P[2].second };
 
    int ans = vect[0].first * vect[1].second - vect[0].second * vect[1].first;
 
    if (ans > 0) {    //반시계
        printf("%d"1);
    }
    else if (ans < 0) {    //시계
        printf("%d"-1);
    }
    else {    //일직선
        printf("%d"0);
    }
}
cs
반응형
반응형

 

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

 

1708번: 볼록 껍질

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽어보고 오시길 추천드립니다!

 

https://rudalsd.tistory.com/66?category=1064608

 

[ 알고리즘 ] 컨벡스 헐 알고리즘(Convex Hull Algorithm)

1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란? 컨벡스 헐 알고리즘은 2차원 평면에 여러 개의 점이 있을 때 그 점들 중 일부를 사용하여 볼록 다각형을 만들고 그 안에 나머지 모든 점을 포함시

rudalsd.tistory.com

 

간단하게 문제 풀이 순서에 대해서 알려드리겠습니다.

 

1. y값이 가장 작은 점을 기준점으로 선택합니다.

 

2. 기준점을 기준으로 반시계 방향으로 점들을 정렬합니다.

 

3. 1번 점과 2번 점보다 다음 점이 반시계 방향에 있다면 stack에 넣고, 그렇지 않다면 2번 점을 빼고 다시 3번의 과정을 반복합니다.

 

[ 소스 코드 ]

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<stack>
 
#define ll long long
 
using namespace std;
 
struct pos
{
    ll x;
    ll y;
};
 
pos arr[100001];
 
int N;
 
ll ccw(pos a, pos b, pos c)        //점이 직선의 반시계방향에 있으면 양수, 시계방향에 있으면 음수, 일직선상이면 0 return
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
 
bool cmp(pos left, pos right)    //가장 왼쪽 아래에 있는 점 찾기
{
    if (left.y != right.y) return left.y < right.y;
    return left.x < right.x;
}
 
bool cmp2(pos left, pos right)    //가장 왼쪽 아래에 있는 점 기준 반시계방향으로 정렬
{
    ll p = ccw(arr[0], left, right);
    if (p > 0) {
        return true;
    }
    else if (p < 0) {
        return false;
    }
    else {
        if (left.y != right.y) return left.y < right.y;
        return left.x < right.x;
    }
}
 
int main()
{
    cin >> N;
    stack <int> s;
    s.push(0);
    s.push(1);
 
    for (int i = 0; i < N; i++) {
        scanf("%lld %lld"&arr[i].x, &arr[i].y);
    }
 
    sort(arr, arr + N, cmp);
 
    sort(arr + 1, arr + N, cmp2);
 
    int next = 2;
 
    while (next < N)
    {
        while (s.size() >= 2) {        //stack에 점이 2개 이상 있다면
            int second = s.top();
            s.pop();
            int first = s.top();
 
            if (ccw(arr[first], arr[second], arr[next]) > 0) {    //다음 점이 직선의 반시계 방향에 있다면
                s.push(second);
                break;
            }
        }
 
        s.push(next);
        next++;
    }
 
    printf("%d", s.size());
cs
반응형
반응형

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

 

17371번: 이사

$(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

생각을 조금만 해보면 쉽게 풀 수 있는 문제입니다.

 

점들 중 하나를 골라 다른 점들과 거리를 비교했을 때 가장 가까운 점은 거리가 0, 가장 먼 거리가 d일 때 평균 거리는 $ \frac{d}{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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cmath>
 
using namespace std;
 
int N;
 
struct pos {
    int x;
    int y;
};
 
pos arr[1000];
int ans;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    double minDist = 9999999;
 
    for (int i = 0; i < N; i++) {
        int x = 0int y = 0;
        double maxDist = 0;
        for (int j = 0; j < N; j++) {    //i번째 점부터 j번째 점까지 거리 중 가장 먼 거리를 maxDist에 저장
            double dist = sqrt(pow(arr[i].x - arr[j].x, 2+ pow(arr[i].y - arr[j].y, 2));
            maxDist = max(maxDist, dist);
        }
        
        if (minDist > maxDist) {        //maxDist 중 가장 짧은 거리를 minDist에 저장하고 idx를 ans에 저장
            ans = i;
            minDist = maxDist;
        }
    }
 
    cout << arr[ans].x << " " << arr[ans].y;
}
cs
반응형
반응형

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<intint> 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
반응형
반응형

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
반응형

+ Recent posts