전체 글188 선분교차판정 코드 (세 점 일직선 포함) [ 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. 백준 14908 / C++ https://www.acmicpc.net/problem/14908 14908번: 구두 수선공 최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답 www.acmicpc.net [ 풀이 ] (T1 S1) (T2 S2) ... (Tn Sn) 이 최적해라고 가정하자. 이제 (T1 S1) (T2 S2)를 교환했을 때 값을 구해서 비교하자. 양식의 차를 비교하면 1식-2식 = T1S2-T2S1이 되고 최적해조건에 따라 T1S2 < T2S1을 만족해야 한다. 즉, T1/S1 < T2/S2 이다. 중간에 있는 (Ti Si)와 (Ti+1, Si+1)을 교환했을 때도 다 소거되고.. 2022. 8. 5. 백준 10277 / C++ https://www.acmicpc.net/problem/10277 10277번: JuQueen The input contains a single test case. It starts with a line containing three integers C, N, and O, where C is the number of cores (1 ≤ C ≤ 4 587 520) to manage, N is the number of frequency steps for each core (1 ≤ N ≤ 10 000) and O is the number www.acmicpc.net [ 풀이 ] 문제조건이 특이하다. 값을 변경시킬때마다 증가하거나 감소시키는데 하나라도 0이나 N이 되면 변경행위를 멈춘다. 예를 들어 2 3 3.. 2022. 8. 5. 백준 3172 / C++ https://www.acmicpc.net/problem/3172 3172번: 현주와 윤주의 재미있는 단어 게임 현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다. 단어 게임을 하던 중, 두 사람은 서로 좋아하지 않는 단어가 있다는 사실을 알게 되었다. 두 단어 A와 B가 있을 때, A가 B www.acmicpc.net [ 풀이 ] 문자열을 우선 정렬해놓자. 이제 정렬후 인덱스로만 보면 처음 문자열의 사전순을 알 수 있다. 이 인덱스를 문자열과 함께 묶어서 들고다니자. 이제 정렬한 문자열을 모두 뒤집는다. 뒤집고 다시 정렬한다. 이제 순회를 시작해보자. 순회의 방향은 항상 뒤집은 문자열이 앞서는 순으로 진행된다. 그럼 좋아하지 않는 순서쌍이 되려면 다음에 보는 문자열의 인덱스가 현재보는.. 2022. 8. 4. 이전 1 ··· 37 38 39 40 41 42 43 ··· 47 다음