https://www.acmicpc.net/problem/2166
2166번: 다각형의 면적
첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.
www.acmicpc.net
해결방법
- 신발끈의 공식을 이용한다.
https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D
신발끈 공식 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 신발끈 공식(―公式)은 좌표평면 상에서 꼭짓점의 좌표를 알 때 다각형의 면적을 구할 수 있는 방법이다. 다각형의 각 꼭짓점의 좌푯값을 교차하여 곱하는 모습이 신발끈을 묶을 때와 같아 이러한 이름이 붙었다.[1] 가우스의 면적 공식이나 사선 공식(斜線 公式)으로도 불린다. 이 공식은 측량이나 임업과 같은 여러 분야에도 응용될 수 있다.[2] 신발끈 공식은 1769년에 수학자 마이스터 알베르트
ko.wikipedia.org
코드
def ccw(x1,y1,x2,y2,x3,y3): #신발끈 공식
return (x1*y2 + x2*y3 + x3*y1) - (y1*x2 + y2*x3 + y3*x1)
num = int(input())
x, y = map(int, input().split())
info = []
for i in range(num - 1):
info.append(list(map(int, input().split())))
tmp = 0
for i in range(num - 2):
tmp += ccw(x,y,info[i][0],info[i][1],info[i+1][0],info[i+1][1])
print(abs(tmp)/2)
'알고리즘' 카테고리의 다른 글
| 백준_2941_크로아티아 알파벳 (0) | 2020.07.08 |
|---|---|
| 백준_2188_축사 배정 (0) | 2020.03.25 |
| 백준_11758_CCW(CCW, 기학와 벡터) (0) | 2020.03.01 |
| 선분 교차 알고리즘 (0) | 2020.02.29 |
| 백준_1057_토너먼트(시뮬레이션) (0) | 2020.02.28 |
댓글