확률 썸네일형 리스트형 BOJ)13352 석양이 진다... 문제: icpc.me/13352 n개의 점들이 주어질 때 두직선만으로 모든 점을 커버가능한지 판별하는 문제이다. 얼마전 코포 B번에서 유사한 문제 http://codeforces.com/contest/849/problem/B 가 등장하였지만 코포 문제는 N^2으로 해결할 수 있었던 반면 이 문제는 N제한이 10만이기 때문에 N^2으로는 풀 수 없다. 그래서 정해를 생각해보다가 도저히 떠오르지 않아서 작년에 들었던 야매 풀이를 떠올려서 풀었다. 풀이는 랜덤하게 두 점을 뽑아서 직선을 하나 만든 다음 나머지 모든 점이 한 직선으로 놓일 수 있는지 확인한다. 여기서 나머지 모든 점이 한 직선으로 놓인다면 당연히 두직선으로 커버되는 것이니 답이 되고 안된다면 위의 행동을 반복한다. 위의 행동을 충분히 반복하였는.. 더보기 이전 1 다음