관리 메뉴

너와 나의 스토리

[BOJ] 11758 CCW 본문

Algorithm/기하

[BOJ] 11758 CCW

노는게제일좋아! 2021. 1. 5. 14:21
반응형

문제: www.acmicpc.net/problem/11758

 

 

문제 풀이:

  • 외적을 이용하자 

  • 이렇게 구해지는 cross product(외적) 값이 [양수 or 음수 or 0]인지에 따라 두 벡터의 상대적인 방향을 확인할 수 있다.

  • 다음과 같이 시계 방향인 것을 CW, 반 시계 방향인 것을 CCW라고 한다.
  • 외적 값이 음수인 경우 CW, 양수인 경우 CCW, 0인 경우 일직선(두 선분이 겹쳐서 일직선을 그림)임을 알 수 있다.

 

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>

using namespace std;

typedef pair<int,int> P;
vector<P> points;

int op(int a, int b){
    return points[a].first*points[b].second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i=0;i<3;i++){
        int x, y;
        cin>>x>>y;
        points.push_back({x,y});
    }
    int cross = op(0,1)+op(1,2)+op(2,0)-op(1,0)-op(2,1)-op(0,2);
    if(cross>0) cout<<"1\n";
    else if(cross<0) cout<<"-1\n";
    else cout<<"0\n";

    return 0;
}
반응형

'Algorithm > 기하' 카테고리의 다른 글

[BOJ] 3878 점 분리  (0) 2019.08.27
[BOJ] 6439 교차  (0) 2019.08.21
[BOJ] 1708 볼록 껍질  (0) 2019.08.20
[BOJ] 2162 선분 그룹  (0) 2019.08.20
[BOJ] 2166 다각형의 면적  (0) 2019.08.20
Comments