boj, 백준) 17387. 선분 교차2 ( C/C++ )
1. 문제 링크 www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2. 문제 개요 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 것이다. 3. 문제 힌트 여러 가지 예외 케이스들을 생각해보자. 가장 기본적인, 두 선분이 교차하는 것에서 시작해서.. 이런 다양한 경우가 있을 수 있다. 어떻게 예외를 처리해야 할까 4. 문제 풀이 많은 예외처리를 다룬 선분 교차 알고리즘을 다른 블로그에서도 많이 올려놓아서 자..
boj, 백준) 12781. PIZZA ALVOLOC ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 2. 문제 개요 볼록 다각형 모양인 피자에서 정점 네 개를 선택하여, 2개의 선분을 만든다. 이 선분이 서로 교차하여 피자가 4조각으로 잘리게 되면 1, 그렇지 않으면 0을 출력하는 프로그램을 작성하자 3. 문제 힌트 선분 교차 알고리즘이다. CCW(외적)을 이용해서 문제를 해결한다. 더 복잡한 2차원 평면에서의 선분교차가 아니고, 볼록 다각형 모서리에서의 정점을 선택하기 때문에 많은 제약이 삭제된다. 종이 ..
boj, 백준) 2166. 다각형의 면적 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 개요 2차원 편명상에 N개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 3. 문제 힌트 외적을 사용하자. 두 벡터를 외적한 것은 두 벡터로 만들어지는 평행사변형의 넓이를 나타냄. 4. 문제 풀이 (다른 블로그에서도 좋은 풀이가 있었으나, 중요한 기초 개념인 것 같아 업로드 합니다.) 우선, 다각형은 엄청 찌그러질 수 있기 때문에... 크기를 쪼개고 쪼개서 넓이를 구한 뒤 ..