BOJ : https://www.acmicpc.net/problem/2699

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
struct point {
    int x, y;
    int p = 0, q = 0;
}p[52];
 
bool cmp(point& a, point& b) {
    if (a.p * b.q != a.q * b.p) return a.q * b.p > a.p * b.q;
    if (a.y != b.y) return a.y > b.y;
    return a.x < b.x;
}
 
int ccw(point& a, point& b, point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int tc; cin >> tc;
 
    while (tc--) {
        int N; cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> p[i].x >> p[i].y;
            p[i].p = p[i].q = 0;
        }
        sort(p, p + N, cmp);
        for (int i = 1; i < N; i++) {
            p[i].p = p[i].x - p[0].x;
            p[i].q = p[i].y - p[0].y;
        }
        sort(p + 1, p + N, cmp);
        stack<int> s;
        s.push(0), s.push(1);
        int next = 2;
        while (next < N) {
            while (s.size() >= 2) {
                int second = s.top();
                s.pop();
                int first = s.top();
                if (ccw(p[first], p[second], p[next]) < 0) {
                    s.push(second);
                    break;
                }
            }
            s.push(next++);
        }
        cout << s.size() << endl;
        vector<point> v;
        while (!s.empty()) {
            v.push_back(p[s.top()]);
            s.pop();
        }
        for (int i = v.size() - 1; i >= 0; i--) cout << v[i].x << " " << v[i].y << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1922번 네트워크 연결  (0) 2020.04.11
BOJ 1197번 최소 스패닝 트리  (0) 2020.04.10
BOJ 1708번 볼록 껍질  (0) 2020.04.07
BOJ 1063번 킹  (0) 2020.04.07
BOJ 14499번 주사위 굴리기  (0) 2020.03.14

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

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
struct point {
    ll x, y;
    ll p = 0, q = 0;
}p[100001];
 
bool cmp(point& a, point& b) {
    if (1LL * a.p * b.q != 1LL * a.q * b.p) return a.q * b.p < a.p * b.q;
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
 
ll ccw(point& a, point& b, point& c) {
    return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (b.y - a.y) * (c.x - a.x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i].x >> p[i].y;
 
    sort(p, p + N, cmp);
    for (int i = 1; i < N; i++) {
        p[i].p = p[i].x - p[0].x;
        p[i].q = p[i].y - p[0].y;
    }
    sort(p + 1, p + N, cmp);
    stack<int> s;
    s.push(0), s.push(1);
    int next = 2;
    while (next < N) {
        while (s.size() >= 2) {
            int second = s.top();
            s.pop();
            int first = s.top();
            if (ccw(p[first], p[second], p[next]) > 0) {
                s.push(second);
                break;
            }
        }
        s.push(next++);
    }
    cout << s.size();
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1197번 최소 스패닝 트리  (0) 2020.04.10
BOJ 2699번 격자점 컨벡스헐  (0) 2020.04.07
BOJ 1063번 킹  (0) 2020.04.07
BOJ 14499번 주사위 굴리기  (0) 2020.03.14
BOJ 14503번 로봇 청소기  (0) 2020.03.13

BOJ : https://www.acmicpc.net/problem/1063

 

시뮬레이션 문제입니다

 

문자 각각 따로따로 구현하면 너무 코드가 길어지고 보기 안좋으니

간단하게 스트링 받아서 비교한 후 바로 사용할 수 있도록 하시면 편하게 해결할 수 있습니다.

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
// R L B T RT LT RB LB
int ml[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int mr[8] = { 0, 0, -1, 1 ,1 ,1, -1, -1 };
string arr[8] = { "R","L","B","T","RT","LT","RB","LB" };
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int tc;
    string str;
    pair<int, int> k, d;
 
    getline(cin, str);
    
    k.first = str[0] - 'A', k.second = str[1]-'0', d.first = str[3] - 'A', d.second = str[4]-'0';
 
    if (str.size() == 7) tc = str[6]-'0';
    else tc = (str[6]-'0') * 10 + (str[7]-'0');
 
    while (tc--) {
        getline(cin, str);
        int check;
        int l = k.first, r = k.second;
        for (int i = 0; i < 8; i++) { if (str.compare(arr[i]) == 0) { check = i, l += ml[i], r += mr[i]; break; } }
 
        if (l >= 0 && l < 8 && r >= 1 && r <= 8) {
            if (!(l == d.first && r == d.second)) {
                k.first = l, k.second = r;
            }
            else {
                int df = d.first + ml[check];
                int ds = d.second + mr[check];
                if (df >= 0 && df < 8 && ds >= 1 && ds <= 8)
                    d.first = df, d.second = ds, k.first = l, k.second = r;
            }
        }
    }
 
    char lastk = k.first + 'A';
    char lastd = d.first + 'A';
    cout << lastk << k.second << endl;
    cout << lastd << d.second << endl;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2699번 격자점 컨벡스헐  (0) 2020.04.07
BOJ 1708번 볼록 껍질  (0) 2020.04.07
BOJ 14499번 주사위 굴리기  (0) 2020.03.14
BOJ 14503번 로봇 청소기  (0) 2020.03.13
BOJ 3709번 레이저빔은 어디로  (0) 2020.03.13

문제마다 다각형 내부점이 되는 기준이 다 다르다

지금 정리하는 기준은 다각형의 선분위에 있는 점 또한 내부점으로 판단한다고 가정한다

 

주어진 점이 다각형의 내부점이 되는지 안되는지 파악하기 전에 

이 다각형을 시계방향이든 반시계방향이든 정렬해서 선분으로 사용할 수 있도록 만들어 놓아야 한다

좌표정렬 : https://junho0956.tistory.com/285?category=879042

 

좌표를 정렬했으니 내부점 판단에 대한 정리 ㄱㄱ

 

베이스는 다음과 같다

임의의 점을 기준으로 반직선을 그었을 떄 다각형의 선분과 교차하는 지점이 발생하게 되는데 이 지점을 횟수 저장하자

모든 다각형의 선분에 대한 탐색이 끝났을 때 교차횟수가 홀수이면 내부점, 짝수이면 외부점으로 판단할 수 있다

 

근데 단순히 저 방식대로만 하면 반례가 많이 생긴다

 

그래서 좀더 정확하게 해결하는 방법을 풀이해보자

 

기준점 => (px,py)

 

첫번째 방법 => ccw를 이용한 내부점 판단

i번째 점과 (i+1)%N점을 기준으로 반직선이 교차하는지 확인

 

다음과 같은 코드로 교차횟수를 증가할지 말지 판단할 수 있다

P[i].y < py && P[(i + 1) % N].y >= py && ccw(P[i], P[(i+1)%N], 기준점) > 0 
P[(i + 1) % N].y < py && P[i].y >= py && ccw(P[(i+1)%N], P[i], 기준점) > 0

 

ccw를 하기전 코드는 단순히 교차를 하는지만 판단하는 부분이고,

ccw의 의미는 선분을 기준으로 기준점이 어디에 있는지 판단하는 부분이 된다

ccw값이 >0 이 되는 즉 기준점이 왼쪽일때 교차횟수를 증가시켜준다

 

두번째 방법

 

ccw를 사용하지 않고 단순히 직선의방정식 y = (y2-y1)/(x2-x1)*(x-x1)+y1 으로도 해결할 수 있다

1
2
3
4
5
6
// 선분이 반직선과 겹치는 경우
if ((y1 < py && py <= y2) || (y2 < py && py <= y1)) {
    double xx = px;
    double check = (py - y1) * (x2 - x1) / (y2 - y1) + x1;
    if (xx <= check) ans++;
}
 

여기에 기준점 자체가 다각형의 선분위에 있는 부분만 따로 고려해주면 ccw를 몰라도 다각형 내부점을 판단할 수 있다  

'algorithm > algorithm' 카테고리의 다른 글

c,c++ 세 점이 주어졌을 때 각도 구하기  (0) 2020.04.10
STL 사용할때 주의할 것(set,map,...)  (0) 2020.04.10
좌표 시계/반시계방향 정렬  (0) 2020.04.07
bit masking (비트마스킹 정리)  (0) 2020.03.14
소인수분해  (0) 2020.02.28

+ Recent posts

티스토리툴바