시간 제한 메모리 제한 0.25초 512MB 문제 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력 L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다. 두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다. 좌표..

선분은 직선 상의 두 점과 그 두 점 사이의 점들로 구성되는 유한인 직선의 부분이다. 간단히 두 점을 잇는 최단거리다. 샤프심 두 개를 책상에 쏟았다. 샤프심을 선분이라고 봤을 때 이 두 가닥의 샤프심의 위치관계를 몇 가지로 나누어 설명할 수 있을까. 우선 두 샤프심이 서로 닿은 경우와 닿지 않은 경우가 있을 것이다. 그리고 닿은 경우에는 겹친 경우도 있을 것이다. 닿지 않은 경우도 나란히 놓여서 샤프심의 길이가 무한히 늘어나도 닿지 않는 특수한 경우와 그렇지 않은 경우로 나눌 수 있다. 1. 벡터의 외적 벡터는 고등수학에 따르면 크기와 방향을 가진 물리량을 의미한다. 쉽게 생각하면 화살표로 볼 수 있다. 길이도 있고 방향도 있다. 선분끼리는 더하거나 뺀다는 연산을 길이만 두고 할 수 있으나 벡터는 방향..

얼마전 볼록껍질 문제를 해결하고 기하 문제에 관심이 생겨 백준 1077번 넓이 문제에 도전해봤다. 새로 배워야 할 개념이 많았는데 넓이를 구하는 기초적인 아이디어를 잘 구현해낸 것 같아 정리해보고자 한다. 1. 볼록다각형의 정의 이 문제를 연구하다가 새로 알게된 사실이다. 볼록다각형은 이웃하지 않는 두 점을 이은 선분이 도형 내부에 존재하는 단순다각형을 말한다. 단순다각형은 다각형을 이루는 변들이 서로 교차하지 않는 다각형을 말한다. 볼록 집합이라는 것도 있는데, 집합 내에서 어떤 두 점을 선택해도 선분이 집합 내부에 그려지게 되는 집합을 말한다. 볼록다각형은 볼록 집합을 이루는 단순다각형이기도 하다. 엄밀한 볼록다각형은 모든 내각의 크기가 180도 미만이어야 한다. 어떤 문제들은 이 조건을 명시하지만 ..

여러 객체가 주어졌을 때, 객체를 둘러싸는 껍질을 만드는 문제다. 적용되는 가장 직관적인 현상은 고무줄이다. 몇 개의 못을 박아두고 못을 전부 안쪽으로 감싸도록 고무줄을 걸어주면 고무줄이 만든 도형이 볼록껍질이 된다. 1. 문제상황 볼록껍질을 만드는 문제상황을 아래 그림을 예시로 생각해 보자. 평면상에 10개의 좌표가 주어져있고 이 점들을 감싸는 최소 면적의 볼록 다각형을 구성하는 점을 특정하는 것이 이 문제의 해가 된다. 해를 구할 수 있는 방법은 모든 점을 방문하며 확인해보는 방법도 있겠으나, 가장 널리 알려진 것은 O(NlogN)의 시간복잡도를 가진 그라함 스캔(Graham's scan)이다. 2. CCW(Counter Clock Wise) 알고리즘 그라함 스캔 알고리즘을 수행하기 위해서는 두 점으..