CCW 썸네일형 리스트형 UVaOJ)12159 Gun Fight 문제:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3311 N개의 power가 존재하는 점이 주어지고 진영을 가르는 직선을 결정하는 두 점이 주어진다. 두 점으로 부터 진영을 갈라서 수가 적은 진영이 수가 많은 진영을 이기도록 최대한 매칭할 수 있는 수를 출력하는 문제이다. ccw를 이요하여 모든 점의 진영을 구해준 뒤 진영이 적은 쪽에서 진영이 많은 쪽으로 두 점 사이의 거리가 R이하이고 Power가 0이상이고 진영이 적은 쪽의 power가 진영이 많은쪽의 power보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다. 123456789101112131415161718192021222324.. 더보기 BOJ)2254 감옥 건설 문제: icpc.me/2254 점(Px,py)를 감싸는 볼록껍질이 최대 몇개까지 가능한지 묻는 문제이다. 기둥들로 Convex hull을 구해준 뒤 해당 껍질이 Px,Py를 감싸는지 ccw로 확인해준 뒤 해당 Convex hull을 이루는 요소들을 전부 지워 준 뒤 이를 반복하여 점(Px,Py)를 감싸는 껍질의 수를 구해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105#includ.. 더보기 이전 1 다음