🧚‍♂️ 알고리즘 🧚‍♂️ - 기하(CCW)

🧚‍♂️CCW(counter-clockwise)🧚‍♂️

평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘

 

CCW 공식

점 A(x1, y1) , B(x2, y2), C(x3, y3)

CCW = (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3)

 

1) CCW 결과 < 0
점 세개 배치 : 시계 방향

2) CCW 결과 == 0
점 세개 배치 :  일직선 방향

3) CCW 결과 > 0
점 세개 배치 : 반시계 방향

 

+) 결과값 / 2

삼각형의 넓이

---

골드 5

17387번: 선분 교차 2

from sys import stdin
x1, y1 = map(int,stdin.readline().split())
x2, y2 = map(int,stdin.readline().split())
x3, y3 = map(int,stdin.readline().split())

# CCW 공식
result = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)

if result > 0: #반시계 방향
    print(1)
elif result == 0:# 일직선 방향
    print(0)
else:# 시계 방향
    print(-1)

---

골드 2

17387번: 선분 교차 2

A-B 선분을 기준으로 점 C,D를 ccw한 값의 곱 / C-D 선분을 기준으로 점 A, B를 ccw

이 둘 다 음수이면 두 선분은 교차함.

(하나는 시계 방향 하나는 반시계 방향일 때)

( 두 선분이 교차할 시 두 ccw의 부호는 서로 반대)

 

그냥 좌표비교로는아노디는구나

 

각 선분이 겹치지 않는 경우는 한 선분의 min값이 다른 선분의 max값보다 클 때 (x,y각각)(전부

from sys import stdin
x1,y1, x2,y2 = map(int,stdin.readline().split())
x3,y3,x4,y4 = map(int,stdin.readline().split())

# CCW 함수 구현
def CCW(x1,y1, x2,y2,x3,y3):
    temp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)
    if temp > 0 : # 반시계
        return 1
    elif temp < 0: # 시계
        return -1
    return 0 #일직선

# 선분 겹침 여부 판별 함수
def isOverlab (x1,y1,x2,y2,x3,y3,x4,y4) :
    if min(x1, x2) <= max (x3, x4) and min(x3, x4) <= max(x1, x2) and min(y1, y2) <= max (y3, y4) and min(y3, y4) <= max(y1, y2):
        return True
    return False

# 선분 교차 여부 판별 함수
def isCross(x1,y1,x2,y2,x3,y3,x4,y4):
    abc = CCW(x1,y1,x2,y2,x3,y3) 
    abd = CCW(x1,y1,x2,y2,x4,y4) 
    cda = CCW(x3,y3,x4,y4,x1,y1) 
    cob = CCW(x3,y3,x4,y4,x2,y2) 
    if abc * abd == 0 and cda * cob == 0:# 선분이 일직선일 때
        return isOverlab(x1,y1,x2,y2,x3,y3,x4,y4) # 겹치는 선분인지 판별
    elif abc * abd <= 0 and cda * cob <= 0: # 선분이 교차하는 경우
        return True
    return False

cross = isCross (x1,y1,x2,y2,x3,y3,x4,y4)

if cross:
    print(1)
else:
    print (0)

---

플래 5

2162번: 선분 그룹

위에 문제 + find/union 함수를 추가해주면 된다 

유니온파인드 오랜만~

from sys import stdin
from collections import Counter
N = int(stdin.readline())
lines = []
parent = [i for i in range(N)] #자기자신부모시작

for i in range(N): # 선들 담기
    x1, y1, x2, y2 = map(int, stdin.readline().split())
    line = [x1, y1, x2, y2]
    lines.append(line)

#부모를찾아
def find(parent, x):
    if parent[x] != x :
        parent[x] = find(parent, parent[x])
    return parent[x]

#한덩어리로만들(부모같)
def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# CCW 함수 구현
def CCW(x1,y1, x2,y2,x3,y3):
    temp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)
    if temp > 0 : # 반시계
        return 1
    elif temp < 0: # 시계
        return -1
    return 0 #일직선

# 선분 겹침 여부 판별 함수
def isOverlab (x1,y1,x2,y2,x3,y3,x4,y4) :
    if min(x1, x2) <= max (x3, x4) and min(x3, x4) <= max(x1, x2) and min(y1, y2) <= max (y3, y4) and min(y3, y4) <= max(y1, y2):
        return True
    return False

# 선분 교차 여부 판별 함수
def isCross(x1,y1,x2,y2,x3,y3,x4,y4):
    abc = CCW(x1,y1,x2,y2,x3,y3) 
    abd = CCW(x1,y1,x2,y2,x4,y4) 
    cda = CCW(x3,y3,x4,y4,x1,y1) 
    cob = CCW(x3,y3,x4,y4,x2,y2) 
    if abc * abd == 0 and cda * cob == 0: # 선분이 일직선일 때
        return isOverlab(x1,y1,x2,y2,x3,y3,x4,y4) # 겹치는 선분인지 판별
    elif abc * abd <= 0 and cda * cob <= 0: # 선분이 교차하는 경우
        return True
    return False


for i in range(N):
    for j in range(i+1, N):
        if isCross(lines[i][0],lines[i][1],lines[i][2],lines[i][3], lines[j][0],lines[j][1],lines[j][2],lines[j][3]): #교차하면
            union(parent, i, j) # union

group = Counter(parent) # 같은 원소의 개수 

print(len(group))# 즉 len 그룹 개수      
print(max(group.values()))#중 제일 큰 거

+

from collections import Counter

Counter 생성자에 문자열을 인자로 넘기면 각 문자가 문자열에서 몇 번씩 나타나는지를 알려주는 객체가 반환

>>> Counter("hello world")
Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

 

 

파이썬 collections 모듈의 Counter 사용법

---

골드 5

2166번: 다각형의 면적

이거이거~ 고등학교때 엄청하던거~

쇼숏

다각형 넓이 구하기: 15 단계 (이미지 포함) - wikiHow

from sys import stdin
N = int(stdin.readline())

x,y = [],[]

for _ in range(N):
    a,b =  map(int, stdin.readline().split()) 
    x.append(a)
    y.append(b)
x.append(x[0])
y.append(y[0])

xr,yr = 0,0
for i in range(N):
    xr+=x[i]*y[i+1]
    yr+=y[i]*x[i+1]
    
print(round(abs((xr-yr)/2),1))