5개의 댓글이 있습니다.
-
-
Kureyo -
전체 중에서 어떤점도 제외하지 않았을때 삼각형 넓이의 총합을 S라 하고,
임의의 꼭지점 i를 중심으로 하는 nC2개의 삼각형 넓이의 총합을 T(i)라고 정의할께요.
그러면 문제에서의 G(i) 는 G(i) = { S - T(i) } / (n-1)C3 입니다.brute force하게 구해도 S,T(i)는 O(n^3)에 구할수 있습니다.
근데 저는 이렇게 짰더니 TLE가 나더군요 ㅜT(i)를 구하는 방법중 하나는 i번째 꼭지점을 (0,0)이 되도록 전체 다각형을 이동한다음에
a < b를 만족하는 모든 a,b값에 대해 a번째 꼭지점과 b번째 꼭지점을 외적하고 그 값의 총합
을 구한 건데요이것들을 묶어서 처리할수 있습니다. :) 이때 T(i)를 O(n)시간에 구할수있고,
그러므로 모든 T(i)를 O(n^2)에 구할수있으며 S = sum(T(i)) / 3이니까 S,T를 O(n^2)시간에 구할 수있...을거같았는데 저는 WA를 받았네요. 뭐가 문제일까요 ;( 방법적으론 대충 이렇게 접근하면 될거같습니다~
EDIT: 제 WA는 해결했습니다. 입력이 정수가 아니라 실수였네요. 에고ㅋ
13년 전 link
-
-
-
Taeyoon_Lee -
n개의 점이 주어졌을 때, 그 중에 3개를 골라서 만들 수 있는 모든 삼각형들의 넓이 합을 O(n^2)에 구하는 방법을 찾으시면 됩니다. (아마도?) 그 방법은 벡터 외적 공식에서 더해지는 값과 빼지는 값을 따로 나눠서 패턴을 잘 찾아보시면, 알아낼 수 있을 겁니다. :D
13년 전 link
-
-
-
Taeyoon_Lee -
음.. 지금 보니, 그 중요한 조건을 안 써놓았군요.. :'(
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
장홍준
AOJ의 'GEOMETRY - 기하 문제 연구' 문제를 오랫동안 풀다가 도저히 안되서 이렇게 질문을 올립니다.
가장 간단한 방법은 모든 정점을 제외시켜보면서(O(N)) 그 정점을 제외한 나머지 정점들의 집합에서 G(i)를 O(N^3)에 구할 수 있으므로 총 O(N^4)이 됩니다. 하지만 N제한이 500이고 Testcase가 있으며 Timelimit가 500ms인 것을 보면 턱없이 부족하죠...
저는 G()가 최소가 되게 하는 어떤 i를 찾았다고 하더라도 그 G(i)를 계산하는데 O(N^3) 밖에 떠오르지 않습니다..ㅠㅠ
이 문제를 생각날 때마다 고민한 지 적어도 3달은 된 것 같네요ㅠㅠ
본 문제에 대해 솔루션이 떠오르신 분들께서 문제에 접근하는 힌트를 주셨으면 합니다.. 부탁드려요~~
13년 전