#include <iostream>
#define lld long long int
using namespace std;
/*
시간 복잡도: O(1)
공간 복잡도: O(1)
사용한 알고리즘: CCW
사용한 자료구조: 배열
*/
int ccw_result;
// 점을 입력받을 구조체를 정의 합니다.
struct info{
lld x, y;
};
// 정의한 구조체를 기반으로 배열을 생성합니다.(3개의 점이 주어집니다.)
info point[4];
// CCW
// 세점의 좌표정보를 순서대로 받습니다.
int ccw(info r, info p, info q){
// 벡터의 외적을 수행합니다.
// 점 p, q에대해 점 r의 x, y를 빼줘서 그래프를 원점에 맞춥니다.
lld first = (p.x - r.x) * (q.y - r.y);
lld second = (p.y - r.y) * (q.x - r.x);
lld result = first - second;
// 1) 1 이면 벡터rp 기준 점 q는 왼쪽에 존재합니다.
if(result > 0) return 1;
// 2) 0 이면 일직선에 존재
else if(result == 0) return 0;
// 3) -1 이면 벡터rp 기준 점 q는 오른쪽에 존재합니다.
else return -1;
}
int main(){
//1. 3개의 점을 순서대로 배열에 입력받습니다.
for(int i=1; i<=3; i++){
scanf("%lld %lld", &point[i].x, &point[i].y);
}
// 2. CCW를 수행합니다.
ccw_result = ccw(point[1], point[2], point[3]);
// 3. 결과 출력
printf("%d\n", ccw_result);
}
문제 아기 상어가 물고기를 잡아 먹을 수 있는 시간을 구하는 문제 ~으아 문제가 정말 길어요~ 1. n 공간의 크기 (2 = n = 20) 2. 지도의 크기 n * n, (1 * 1 에는 최대 물고기가 1마리 있습니다.) 3. 상어, 물고기 크기는 모두 자연수입니다. 4. 지도 정보 1) 상어 - 위치 - 상어의 위치는 숫자 9로 표시...
문제 - n개의 점(x, y로 나타냅니다.)으로 이루어진 다각형의 면적을 구하세요 - n (1 ≤ n ≤ 1만) 정점의 수 1만 이하 - 좌표의 크기 10만이하 - 시간 제한 2초 - 문제 링크 - 접근 과정 1. 다각형의 면적?, CCW CCW(벡터의 외적)은 두 벡터가 이루는 평행사변형의 넓이를 계산합니다. - 만약 오목한 부분이 있다면? ...
1. CCW 란 - CCW (Counter Clock Wise, 원래 의미는 시계 반대방향) 는 3개의 점 r, p, q가 있을때 벡터 rp를 기준으로 점 q가 어느 위치(왼쪽, 같은 직선, 오른쪽)에 있는지를 판별하는 방법입니다. - 벡터의 외적입니다. - 외적은 교환법칙이 성립하지 않습니다. AB 와 BA가 같지 않습니다. - 기하 알고리즘의 가장 기본...
문제 - n개의 정점이 주어집니다. - 3개의 줄에 좌표가 주어집니다. - 3개의 줄에 주어진 각각의 좌표가 n개의 정점으로 구성된 다각형 내부에 있는지 외부에 있는지 판별하세요 - n (1 ≤ n ≤ 1만) 정점의 수 1만 이하 - 좌표의 크기 10억이하 - 사용한 알고리즘 CCW, 선분교차 - 시간 제한 2초 - 문제 링크 - 접근 과정 ...
문제 - n개의 정점과, m 개의 간선이 주어집니다. - m개의 줄에는 간선의 정보 3정수 a, b, c가 주어집니다. a-b로 가는데 무게 제한이 c라는 의미입니다. - 무게 제한 c 이하로만 이동할 수 있습니다. - 모든 간선은 양방향 입니다. - 마지막 줄에는 출발 정점과, 도착 정점이 주어집니다. - n, m(1 ≤ n,m ≤ 10만) 정점과 간선의...