Problem Solving/KOITP21 친구 수 세기 - USACO_2014MAR_FRIENDS 문제 링크(koitp.org/problem/USACO_2014MAR_FRIENDS/) 2017. 2. 12. 가장 거리가 먼 두 점 - FARTHEST_PAIR 문제 링크(koitp.org/problem/FARTHEST_PAIR/)답이 되는 두 점의 쌍은 컨벡스헐 위에 존재한다.컨벡스헐 위의 점들에 대해서 로테이팅 캘리퍼스로 답을 탐색한다.로테이팅 캘리퍼스에서 판단 기준은 유클리드 거리가 아닌 CCW로 판단한다.구간의 양 끝이 [A, B]라고 한다면,A번째 점과 A+1번째 점을 잇는 선분과, B번째 점과 B+1번째 점을 잇는 선분의 외적을 계산해 방향이왼쪽으로 계속 꺽이다가 오른쪽으로 꺽이게 되는 순간 멈추면 된다. 2017. 2. 9. Convex Hull - CONVEXHULL 문제 링크(koitp.org/problem/CONVEXHULL/) ※ 비교 함수(i, j) : i < j인지의 여부 극단점을 기준으로 1) left turn이면 ok 2) 일직선상에 있고, 극단점으로부터의 거리가 i가 더 멀면 ok (PC에서는 아래 코드를 클릭하면 더 선명하게 보인다.) 2017. 2. 8. 파티 참석하기 2 - PARTY2 문제 링크(koitp.org/problem/PARTY2/)STL 없이 코드를 작성해보았다. 우선, 이 문제에서 구하고자 하는 것은 max(dist(X→a)+dist(a→X))이다. dist(X→a)는 X번 학생의 기숙사 방에서 a번 학생의 기숙사 방에 이르는 최단거리이다. 따라서 이 문제는 주어진 그래프에 대해 dist(X→a)와 dist(a→X)를 계산하면 풀 수 있다. dist(X→a)는 주어진 그래프에서 점 X를 시작점으로 다른 점들에 이르는 최단 거리를 구하면 된다. dist(a→X)는 주어진 그래프의 간선 방향을 뒤집은 다음(간선의 시작점과 끝점을 바꿈), 위와 마찬가지로 계산하면 된다. 정리하면, 원래 주어진 그래프(G1)에 대해 점 X에서 단일 출발점 최단경로 알고리즘을 수행하고, 주어진 그.. 2017. 2. 7. 호감도 - GOOD_FEELING 문제 링크(koitp.org/problem/GOOD_FEELING)랜덤으로 선분을 결정한 다음, 답의 여부를 확인하는 걸 상수번 반복.20% 이상이어야 하기 때문에 답이 YES라면 높은 확률로 추출 가능.C++은 빨라서 100점이 나오는데, Python은 TLE 나온다ㅠㅠ 하지만 답은 다 맞음. 2017. 2. 5. 이전 1 2 3 4 5 다음
