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



좌표 평면위의 점의 최장 거리를 이루는 두 점은 하나의 볼록 껍질 위에 존재한다는 것을 이용해서 푼다.


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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct P{
    ll x, y;
    P operator- (P a) { 
        return { x - a.x, y - a.y };
    }
}b[200001];
vector<P> v;
ll ccw(P p1, P p2) {
    ll ret = p1.x*p2.y - p2.x*p1.y;
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
ll ccw(P c, P a, P b) {
    return ccw(a - c, b - c);
}
ll sqdis(P p1, P p2) {
    return (p1.x - p2.x) *(p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmp(P p1, P p2) {
    ll ret = ccw(b[0], p1, p2);
    if (ret > 0) return true;
    else if (ret < 0) return false;
    else {
        if (sqdis(b[0], p1) < sqdis(b[0], p2)) return true;
        else return false;
    }
}
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int Min = 111111111, idx = 0; //y값 최소 다음 x값 최소
        for (int i = 0; i < n; i++) {
            cin >> b[i].x >> b[i].y;
            if (b[i].y < Min) {
                Min = b[i].y;
                idx = i;
            }
            else if (b[i].y == Min) {
                if (b[i].x < b[idx].x) idx = i;
            }
          }
        swap(b[0], b[idx]);
        sort(b + 1, b + n, cmp);
        
        //graham scan
        for (int i = 0; i < n; i++) {
            while (v.size() >= 2 && ccw(v[v.size() - 2], v[v.size() - 1], b[i]) <= 0) {
                v.pop_back(); 
            }
            v.push_back(b[i]);
        }
        v.push_back(b[0]); //마지막에 첫점 연결
 
        ll ans = -1;
        int j = 1, st, en;
        for (int i = 0; i < v.size()-1; i++) {
            while (i != j && ccw(v[i + 1] - v[i], v[j + 1] - v[j]) > 0) {
                j++;
                if (j >= v.size() - 1) j = 0;
            }
            ll dist = sqdis(v[i], v[j]); //ccw가 양수가 아니게 되는 순간마다 거리 측정
            if (ans < dist) {
                st = i;
                en = j;
                ans = dist;
            }
        }
        printf("%lld %lld %lld %lld\n", v[st].x, v[st].y, v[en].x, v[en].y);
        v.clear();
    }
    return 0;
}
cs


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

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

백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19
백준 1926번 그림 (C++)  (0) 2019.08.19
백준 2458 키 순서 C++  (0) 2019.08.16
백준 1806 부분합 C++  (0) 2019.08.16
백준 11404 플로이드 C++  (0) 2019.08.16

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

+ Recent posts

티스토리툴바