[CF 1163C2] Power Transmission (Hard Edition) - 2000 문제 설명 : 풀이 : 주의할 점 : 배울 점 : 2차원 좌표평면 상의 직선을 표현하기 위해서는 일반적으로 기울기와 y절편이 필요하다. 그런데 기울기나 y절편 모두 정수가 아닌 유리수 형태일 수도 있다. c++에서는 소수의 정밀도 문제 때문에 유리수를 그대로 사용하는 것은 위험하다. 따라서 이런 경우에는 일반적으로 두 정수로 표현되는 기약분수 꼴로 나타낸다. 여기서 나는 기울기와 y절편 모두 유리수가 될 수 있으므로 (기울기의 분모,기울기의 분자, y절편의 분모, y절편의 분자) 총 4개의 dimension이 필요할 것 같아서 너무 복잡하다고 생각했다. 그런데 사실 일차함수에서는 단 3개면 된다. 우리가 일반적..
[Codeforces 1028C] Rectangles - 1600 문제 설명 : n개의 직사각형의 좌표가 주어진다. n개의 직사각형중에서 최소 (n-1)개의 직사각형의 교집합의 좌표를 구하면 된다. 풀이 : 최소 (n-1)개의 직사각형의 교집합을 구해야 한다. 이는 다른 말로 표현하면 포함하지 않을 단 1개의 직사각형을 고르면 된다는 뜻이다. n개의 직사각형을 모두 살펴보면서 현재 보는 직사각형을 포함하지 않으면 나머지 (n-1)개의 직사각형들은 교집합을 가질 수 있는지 확인하면 된다. 확인하는 연산은 단 O(1)만에 가능하다. 전처리로 1~i까지의 직사각형의 교집합을 저장하는 pref[]배열, (i+1)~n까지 직사각형의 교집합을 저장하는 suf[]배열을 만들어놓고 1~(i-1)범위의 교집합( = pr..