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

두 선분이 주어질 때 선분의 교차를 판별하는 법에 대해서 알아보자.


각 선분은 2개의 정점으로 주어질 것이다.


각 선분을 가지고 다른 선분과 ccw를 돌린다. 


ccw(선분 하나와 다른선분의 정점) * ccw(선분 하나와 다른 선분의 다른 정점) <=0 and ccw(다른 선분과 선분 하나의 정점) * ccw(다른 선분과 선분 하나의 다른 정점) <=0


등호는 선분이 서로 관통하지는 않고 딱 만났을 경우이다. 여기서는 이 경우 또한 교차했다고 본다.


위의 조건까지 성립하게 되면, 물리적으로는 아니지만 두 선분이 이루는 각도 상으로는 만날 수 있는 조건을 충족한다.


선분이 아니라 직선이었다면 위의 조건까지만 충족해도 만나는 것이다. 하지만 선분이기 때문에, 어떻게 놓여있느냐에 따라서 만날 수도 있고 아닐 수도 있다.


선분 하나의 두 x좌표가 다른 선분의 두 x좌표보다 모두 작거나, y좌표 또한 이렇다면 두 선분은 만나지 못한다. 이를 코드로 표현하면 다음과 같다.



(ccw, isCross 함수를 보면 된다. main에서 특별히 뭘 하는 건 없음)


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
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
struct LINE {
    int x1, y1, x2, y2;
 
};
LINE L[3001];
 
 
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 = 0; i < n; i++)
        cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
    
 
    return 0;
}
cs


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

'Computer Science > Algorithm Theory' 카테고리의 다른 글

Counting Sort (C++)  (0) 2019.08.23
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19
기하 및 그래프 알고리즘 간단 정리  (0) 2019.08.17
CCW  (0) 2019.08.10
시간복잡도  (0) 2019.08.10

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



CCW를 활용하여 면적을 구하는 문제이다.


여러개의 좌표가 주어질 때, CCW를 활용해서 면적을 구하는 방법에도 여러가지가 있다.



필자가 구현한 것처럼, 다각형을 이루는 점 하나를 중심으로 CCW를 돌리는 방법이 있고,


원점과 같은 다각형 외부의 정점을 잡아서 CCW를 수행하는 방법이 있다.


CCW 함수가 시행되는 횟수의 차이가 있을 것이다.



이 문제에서 또 유의할 것은, 어떤 자료형을 사용할 것이냐이다. n이 10만을 넘어가기 때문에, 면적을 구하는 과정에서 int 범위 밖으로 나갈 수 있다.


따라서 long long을 사용해주면 되겠다.



면적을 구하는 중간에 음수가 나오더라도, 계산 중간중간에 나오는 양수들 때문에 알아서 절댓값은 넓이만큼 구해지게 된다. 따라서 결과에서만 절댓값을 취하고, 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>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
}p[10001];
int n;
 
ll ccw(POT p1, POT p2, POT p3) {
    ll ret;
    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);
    return ret;
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    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
//좌표값 정수
#include<iostream>
#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}; }
}p[10001];
 
int n;
ll ccw(POT p1, POT p2) {
    return p1.x*p2.y - p1.y*p2.x;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}
cs


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

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

백준 6439 교차 C++  (0) 2019.08.11
백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10

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



CCW 알고리즘을 그대로 구현해주면 된다.


p1 p2 p3가 있을 때, 순서대로 선분을 만들면 선분 p1p2, 선분 p2p3가 생긴다.


나중에 생긴 선분 p2p3가 선분 p1p2에 대해서 어떻게 위치하고 있는지 생각해보면 된다.


p2를 p1으로 평행이동해서 벡터를 생각해본다면 이해가 좀 더 쉽다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//좌표값 정수
#include<iostream>
using namespace std;
typedef long long ll;
struct POT {
    int x, y;
};
int ccw(POT p1, POT p2, POT p3) {
    ll ret;
    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 0;
    else return 1;
}
int main(void) {
    POT p1, p2, p3;
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
    cout << ccw(p1, p2, p3);
    return 0;
}
cs






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
 
using namespace std;
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) > 0) return 1;
    else if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) < 0) return -1;
    else
        return 0;
}
 
int main(void) {
 
    int x1, y1, x2, y2, x3, y3;
 
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
 
    cout << ccw(x1, y1, x2, y2, x3, y3) << '\n';
    
    return 0;
}
cs


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

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

백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09

+ Recent posts

티스토리툴바