4mili Dev Blog

def find(a): if parent[a]==-1: return a return find(parant[a]) def union(a,b): fa = find(a) fb = find(b) if fa==fb: print("이미 같은 집합임") return False parent[fa]=fb return True

좌표평면에 점 세 개가 있을 때, 세 점이 순서대로 반시계 방향을 이루는지 확인하는 방법. A, B, C점이 있을 때, A->B->C가 반시계 방향을 이룬다면, 벡터 AB와 벡터 AC를 외적하여 그 결과값의 부호가 양수이다.만약 한 직선 위에 세 점이 모두 존재한다면 0이다 만약 시계방향을 이룬다면 부호가 음수이다. 즉,A = (x1,y1), B = (x2,y2), C = (x3,y3)이라고 했을 때, 벡터 AB와 벡터 AC를 외적한 결과의 계수는 (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)이므로 CCW를 코드로 나타내면 다음과 같다.def CCW(x1, y1, x2, y2, x3, y3): t = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1) if t>0: ..