Dev_Diary

https://www.acmicpc.net/problem/1027 현재 서있는 건물 꼭대기에서 다른 건물을 볼 수 있는 조건은 내가 서있는 건물과 보고자 하는 건물 사이의 건물들이 시야를 가리지 않는 것입니다. 즉 서있는 건물의 꼭대기와 보고자 하는 건물의 꼭대기를 이은 선분이 다른 건물과 교차하지 않으면 됩니다. 다만 이런 식으로 진행하면 앞선 건물이 다음 건물을 가리는 경우를 고려할 수 없으니 다른 방법을 생각해야 합니다. 왼쪽에 있는 건물의 왼쪽에 있는 건물을 보려면 내가 서있는 건물의 꼭대기에서 가까운 왼쪽에 있는 건물의 꼭대기를 향해 반직선을 그었을 때 반직선의 반시계 방향에 건물의 꼭대기가 있다면 이 건물은 앞선 건물에 가려 보이지 않습니다. 반대로 반직선의 시계 방향에 건물의 꼭대기가 있다면..

https://www.acmicpc.net/problem/2254 2254번: 감옥 건설첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.www.acmicpc.net볼록 껍질 ( convex hull ) 알고리즘과 임의의 점이 다각형 안에 존재하는지 찾는 알고리즘을 함께 사용하면 풀 수 있습니다. 볼록 껍질 알고리즘은 아래 링크를 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 ..

https://www.acmicpc.net/problem/1688 1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있다 www.acmicpc.net 일반적인 볼록 다각형이라면 단순히 모든 직선과 사람의 좌표를 CCW 알고리즘을 통해 일관된 방향이 나오는지 체크하면 되지만 오목 다각형을 포함하는 문제라면 그렇게 쉽게 풀리지 않습니다. (0, 0) 에서 출발해서 시계 방향으로 체크한다고 가정하겠습니다. 0~3 직선까지는 직선-점의 방향이 시계방향이지만 4 직선에서는 반시계방향인 것을 알 수 있습니다. 즉 오목 다각형을 포함하는 문제에서..

https://www.acmicpc.net/problem/1858 1858번: 기울기가 가장 큰 두 점 평면상에 N개의 서로 다른 점들이 주어져 있을 때, 그 중 임의의 두 점을 지나는 직선의 기울기의 절댓값이 가장 큰 두 점을 찾고 싶다. 두 점의 좌표가 (x1, y1), (x2, y2) 라고 할 때, 기울기의 절댓 www.acmicpc.net 완전탐색으로 알고리즘을 짜면 시간초과가 걸리니 적당히 샘플링 할 방법을 찾아야합니다. 여기서 어느 점들을 골라 비교하면 될까를 생각하게 되는데, 결론적으로는 x 축을 기준으로 인접한 점들을 비교해주면 됩니다. 어떤 좌표군을 탐색하겠습니다. 우리는 해당 좌표군을 2진 탐색의 방식으로 가장 기울기의 절댓값이 큰 선분이 어떤 식으로 존재하는지 탐색하겠습니다. x 축을..