기하7 백준 25315 / C++ https://www.acmicpc.net/problem/25315 25315번: N수매화검법 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다. N수매화검법은 2 www.acmicpc.net [ 풀이 ] 선분교차여부는 CCW로 잘 구해주면 된다. 이제 (m+1)*w[i] 이 부분을 처리해야 한다. 서로 교차하는 것끼리 묶었다고 해보자. 묶은 것들은 m이 최대부터 시작하게 된다. (안벤 베기의 개수니까) 벤 후엔 계속 m은 감소하므로 따라서 묶은것들은 가중치가 작은것부터 처리해야 값이 최소가 된다. (그리디하게 최소는 최대와, 최대는 최소와 만나야 곱들의 합이 최소가 됨) 이제 구현해보.. 2022. 8. 8. 선분교차판정 코드 (세 점 일직선 포함) [ Code ] using ll = long long; using pll = pair; #define x first #define y second int ccw(pll a, pll b, pll c) { ll t = (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x); return (t > 0) - (t b) swap(a, .. 2022. 8. 7. 백준 1027 / C++ https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net [ 풀이 ] 1. 건물 s와 건물 e가 서로 보일 조건은 두 건물 사이의 건물들의 높이가 두 건물을 이은 직선보다 아래에 있으면 된다. 직선 식을 세워서 보이는지 확인하는 check 함수를 만들어준다. O(N)에 처리할 수 있다. 2. 모든 건물쌍에 대해 check 를 만족하면, cnt[s]와 cnt[e]를 갱신해준다. cnt[i]는 건물i에서 볼수있는 건물의 수이다. 3. 시간복잡도는 각 쌍 N.. 2022. 7. 7. 이전 1 2 다음