승형님의 블로그

선분 L1과 L2가 주어졌을 때, 두 선분이 교차하는지 판정하는 알고리즘. typedef pair pii; pair L[2]; int func(pair L1, pair L2); int CCW(pii A, pii B, pii C); int func(pair L1, pair L2) { pii p1 = L1.first, p2 = L1.second, p3 = L2.first, p4 = L2.second; int ccw1 = CCW(p1, p2, p3) * CCW(p1, p2, p4); int ccw2 = CCW(p3, p4, p1) * CCW(p3, p4, p2); if (ccw1 == 0 && ccw2 == 0) { if (p1 > p2) swap(p1, p2); if (p3 > p4) swap(p3, p4)..

2차원 좌표평면에 세 점 $p_1, p_2, p_3$가 주어질 때, 다음 식을 통해 $p_1 \to p_2 \to p_3$로 형성되는 선분의 방향성을 알 수 있다. 벡터의 외적 $S = (x_1y_2 + x_2y_3 + x_3y_1) - (x_2y_1 + x_3y_2 + x_1y_3)$ $if $ $ S 0$, 반시계방향 int CCW(pair A, pair B, pair C) { int a = A.first * B.second + B.first * C.second + C.first * A.second; int b = B.first * A.second + C.first * B.second + A.first * C.second; ..

$p_1, p_2, ... p_k$를 $N$의 소인수라고 할 때, Euler's phi function에 의해 다음이 성립한다. $\Phi (N) = N \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2})\times ... \times (1 - \frac{1}{p_k}) $ 이때, $\Phi(N)$은 1 이상 $N$이하의 수 중 $N$과 서로소인 수의 개수를 의미한다. $p_1, p_2, ... p_k$는 모두 $N$의 소인수이기 때문에 결과값은 항상 정수임을 확인할 수 있다. 이를 구현하면 다음과 같다. 수를 소인수 분해 한 뒤, 소인수들로 식을 형성한다. https://int-p.tistory.com/21 정수의 소인수분해 알고리즘 정수 K를 소인수분해하여..

https://codeforces.com/contest/1766 Dashboard - Educational Codeforces Round 139 (Rated for Div. 2) - Codeforces codeforces.com A. Extremely Round 요약 수를 구성하는 자릿수 중 0이 아닌 수를 단 하나만 가지는 양수의 개수를 구한다. 1. 1 ~ 9, 10 ~ 99, 100 ~ 999 ...로 딱 떨어지는 수를 센 뒤 더해주는 방식을 택한다. 2. 한 자릿수마다 조건에 부합하는 수는 9개이다. #include using namespace std; int t, N; int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> t; whi..

https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 요약 주어진 조건으로 처리할 수 없는 좀비가 C개 이하인지 여부를 구한다. 1. 좀비와의 거리와 체력, 기관총의 사거리와 공격력, 지뢰의 개수가 주어진다. 만약 좀비의 체력이 기관총을 쏜 횟수 * 기관총의 공격력보다 높다면, 지뢰를 사용하여야 한다. 2. 기관총을 쏜 횟수 * 기관총의 공격력을 누적합으로 psum이라는 배열로 관리한다. 지뢰와 기관총을 동시에 사용할 수 없으므로, 지..

https://codeforces.com/contest/1771 Dashboard - Codeforces Round #837 (Div. 2) - Codeforces codeforces.com A. Hossam and Combinatorics 요약 n개의 정수로 이루어진 수열이 주어진다. $\left| a_{i} - a_{j}\right|$이 수열에서 최대인 쌍 (i, j)의 갯수를 구한다. 1. $\left| a_{i} - a_{j}\right|$의 최댓값이 0인 경우, 0이 아닌 경우로 나누어 풀 수 있다. 만약 $\left| a_{i} - a_{j}\right|$의 최댓값이 0인 경우, n개의 정수가 모두 같은 수일 때이므로 답은 $n *(n-1)$이 된다. 2. $\left| a_{i} - a_{j..