기하학3 Convex Hull과 CCW * Convex Hull: 볼록 껍질 * CCW: counter clockwise, 시계 반대 방향 외적을 이용하는 기하학 문제에서 쓰인다. 주어진 점을 모두 포함하는 볼록 다각형의 꼭짓점을 찾아야 한다. 1. 볼록 껍질의 한 꼭짓점을 찾는다. y좌표가 가장 크거나 가장 작은 점, x좌표가 가장 크거나 가장 작은 점 중 아무거나 고르면 된다. 해당 점을 모두 포함하는 MBR(Minimal Bounding Rectangle)과 볼록 껍질이 무조건 접해야하기 때문 이때는 간단한 비교 함수를 사용해 점을 정렬하고 첫 번째 원소를 기준점으로 잡는다. 2. 기준점을 기준으로 다른 점을 시계방향으로 정렬한다. 이때 외적이 쓰인다. 벡터 OA와 OB의 외적 < 0 ⇒ O를 기준으로 A, B가 시계방향으로 존재한다. .. 2021. 4. 9. 기하학 (2) 계산 문제들 1207번 고층건물 - 기울기16190번 Rising Sun - 좌표, 기울기16115번 팬이에요 - 삼각함수1798번 원뿔좌표계상의 거리 - 좌표, 삼각함수1207번 고층 건물같은 간격으로 떨어져 있는 건물의 높이가 정수로 주어질 때각 건물의 옥상에서 보이는 다른 건물의 개수 중 최댓값 출력현재 건물과 보려고 하는 건물의 옥상을 이은 선분에 다른 건물이 교차하거나 만나면 안 된다. 즉, 현재 건물의 옥상을 점 A라 하고현재 건물에서 볼 수 있는 건물의 옥상을 왼쪽에서 오른쪽 순서로 각각 점 B1, B2, ...라 하면선분 AB1, AB2, ...의 기울기가 순서대로 증가해야 함 기울기가 같으면 안 됨. 8에서는 7만 보이고 6은 볼 수 없다. 높이가 극댓값인 건물만 보면 틀린다.낮은 건물에서 다른 건물.. 2021. 3. 15. 기하학 (1) 고등수학 재밌다. 더보기고민을 안하고 풀어도 됨 바깥 삼각형의 중심 벡터 열심히 계산해서 연립방정식 풀면 된다 너무 재밌따. 피자 배치 닮음비 계산하고 지수 늘려주면서 K번째 피자를 찾는다. 외계인의 침투 모의고사 18번 문제 느낌임 아니면 26번,, 대충 먼말인지 알지 Cows 다각형은 삼각형으로 나눌 수 있다. 삼각형의 넓이는 K-고등수학을 배웠다면 구할 수 있다. 여기선 다만 점을 정렬해줘야 하는데 이때 컨벡스헐 개념이 필요했던 것 같네컨벡스헐 솔직히 아직 완벽히 알지 못하는 상태라 다음에 정리해줘야겠다. 2021. 1. 19. 이전 1 다음
