꾸꾸리

문제 출처:https://www.acmicpc.net/problem/6439 6439번: 교차 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, xstart ystart xend yend xleft ytop xright ybottom로 이루어져 있다. (xstart, ystart)는 선분의 시작점, (xend, yend)는 www.acmicpc.net 문제 입력으로 주어진 선분과 직사각형이 교차하는지 아닌지를 구하는 프로그램을 작성하시오. 위의 그림에서 선분의 시작점은 (4,9), 끝점은 (11,2) 이며, 직사각형의 왼쪽 위 좌표는 (1,5), 오른쪽 아래 좌표는 (7, 1)이다. 또, 선분과 직사각형은 교차하지 않는다. 선분과 직사각형이 교차하려면 적어도 한 ..

문제 출처:https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x..

1. CCW 알고리즘 이란 점 A, B, C 세 점이 존재하였을 때, 이 세 점의 방향관계를 구하는 알고리즘이다. A, B, C를 연결하였을 때, 반시계 방향일 경우 양수를, 시계 방향일 경우 음수를, 직선일 경우 0을 반환한다. 이 세점의 방향관계를 구하기 위해서 세 점을 두 개의 벡터로 표현하고, 외적을 통하여 그 값이 음수인지 양수인지 0인지를 확인하는 과정이 필요하다. 그럼 우선 외적에 대해 알아보자. 2. 외적 두 벡터 A와 B에 모두 수직인 벡터 A X B를 A, B의 외적이라고 정의한다. 외적의 크기는 |A||B|sinθ이고, 두 벡터가 만드는 평행사변형의 넓이와 같다. 두 벡터의 외적의 방향은 오른손의 법칙을 따른다. 교환법칙이 성립하지 않는다. ( A X B != B X A) A X B ..