다각형의 면적 2166 

    
 https://www.acmicpc.net/problem/2166
다각형의 면적을 구하는데 고등학교때 기하와 벡터 배울때 한 거 떠올려서 풀었다.
신발끈 공식. 오랜만에 생각해본다.
공식만 알면 그냥 풀리는 골드 중에서 제일 쉬운 문제 아닐까
 

```python
N=int(input())
points=[]
for i in range(N):
    x,y=map(int,input().split())
    points.append((x,y))

a1,a2=points[0][0],points[0][1]
area=0
for i in range(1,N-1):
    b1,b2=points[i][0],points[i][1]
    c1,c2=points[i+1][0],points[i+1][1]
    area+=(a1*b2+b1*c2+c1*a2-(a2*b1+b2*c1+c2*a1))/2

print(round(abs(area),1))
```
하다가 오목한 도형일경우 빼줘야 하는 경우 때문에 전체 계산후 abs를 해야 했는데 그 부분을 고려 안해서 조금 고민했다.

관련해서 찾아보다가 볼록 껍질이라는 개념이 있다고 해서 흥미로워서 덧붙여둠.

---

# 볼록껍질 관련 설명
볼록껍질(Convex Hull) 알고리즘은 2차원 평면 위에 주어진 점들 중에서 이 점들을 모두 포함하는 가장 작은 볼록 다각형을 찾는 문제를 해결하기 위한 알고리즘입니다. 쉽게 말해, 주어진 점들 중 가장 바깥쪽에 위치한 점들을 연결하여 만들어진 다각형을 찾는 것입니다.

### 볼록껍질의 정의
볼록껍질은 다음과 같은 성질을 가집니다:
- 볼록 다각형: 이 다각형의 각 내부각은 180도보다 작으며, 다각형의 내부에 있는 임의의 두 점을 잇는 선분이 항상 다각형 내부에 위치합니다.
- 주어진 점 집합을 모두 포함하는 최소의 다각형입니다.

### 볼록껍질 알고리즘의 종류
여러 가지 알고리즘이 있지만, 대표적인 볼록껍질 알고리즘은 다음과 같습니다:

1. **그레이엄 스캔(Graham Scan)**
   - 그레이엄 스캔은 점들을 기준점에서 시계 방향으로 정렬한 다음, 스택을 이용해 볼록껍질을 구성하는 방식입니다.
   - 주요 단계:
     1. 주어진 점들 중 가장 아래쪽에 있는 점을 기준점으로 설정합니다.
     2. 다른 점들을 기준점에서 시계 방향으로 각도에 따라 정렬합니다.
     3. 스택에 점들을 추가하면서 볼록껍질의 일부가 되지 않는 점들을 제거해 나갑니다.
   - 시간 복잡도: \(O(n \log n)\)

2. **자비스의 선물 포장 알고리즘(Jarvis March, Gift Wrapping)**
   - 선물 포장 알고리즘은 마치 포장지를 돌려가며 선물을 포장하는 방식처럼, 점들을 하나씩 선택해 가면서 볼록껍질을 만들어 나갑니다.
   - 주요 단계:
     1. 가장 왼쪽에 있는 점부터 시작하여 볼록껍질의 한 점을 선택합니다.
     2. 현재 선택한 점에서 가장 멀리 떨어진 점을 찾아 선택합니다.
     3. 선택한 점이 출발점으로 돌아올 때까지 이 과정을 반복합니다.
   - 시간 복잡도: 최악의 경우 \(O(nh)\) (여기서 \(h\)는 볼록껍질에 속하는 점의 수)

3. **QuickHull**
   - QuickSort와 유사한 방식으로 동작하는 알고리즘입니다.
   - 주어진 점들을 이용해 볼록껍질의 왼쪽과 오른쪽 점을 선택하고, 그 사이에 있는 점들을 재귀적으로 처리하여 볼록껍질을 구합니다.
   - 시간 복잡도: 평균적으로 \(O(n \log n)\), 최악의 경우 \(O(n^2)\)

4. **Chan’s Algorithm**
   - 이 알고리즘은 그레이엄 스캔과 자비스 알고리즘을 결합한 방식으로, \(O(n \log h)\) 시간 복잡도를 가집니다.
   - \(h\)는 볼록껍질에 포함된 점의 수로, 이 알고리즘은 점들이 적은 경우에 더 효율적입니다.

### 예시
만약 다음과 같은 점들이 주어졌다고 가정해봅시다: 
```
(0, 0), (1, 1), (2, 2), (3, 1), (2, 0), (0, 2)
```
이 점들을 포함하는 볼록껍질은 (0, 0), (0, 2), (3, 1), (2, 0)을 연결한 다각형이 됩니다. 볼록껍질 알고리즘은 이 점들을 찾고, 이 점들을 연결한 다각형을 반환하게 됩니다.

### 실제 활용 예
볼록껍질 알고리즘은 컴퓨터 그래픽스, GIS(지리 정보 시스템), 기하학적 문제 해결 등 여러 분야에서 활용됩니다. 예를 들어, 지도에서 주어진 도시들 중 가장 외곽에 있는 도시들을 찾아 경계를 표시하는 데 이용될 수 있습니다.

이상으로 볼록껍질 알고리즘의 개요를 설명드렸습니다. 알고리즘을 구현하거나 더 깊이 있는 내용을 알고 싶다면, 특정 알고리즘에 대해 더 질문해 주세요!

댓글

댓글 쓰기

이 블로그의 인기 게시물

js 스트링에서 요소 갯수 세기

이상하다 https://stackoverflow.com/questions/881085/count-the-number-of-occurrences-of-a-character-in-a-string-in-javascript If you're looking for the commas: (mainStr. split ( "," ). length - 1 ) //3 If you're looking for the str (mainStr. split ( "str" ). length - 1 ) //4   console . log (( "str1,str2,str3,str4" . match ( /,/g ) || []). length ); //logs 3 console . log (( "str1,str2,str3,str4" . match ( new RegExp ( "str" , "g" )) || []). length ); //logs 4
Read more »

STUDY

@GetMapping("/proxy-download") public ResponseEntity<Resource> proxyDownload() {     String sourceUrl = "https://example.com/file-to-download.bin";     ResponseEntity<byte[]> response = restTemplate.exchange(         sourceUrl,         HttpMethod.GET,         null,         byte[].class     );     byte[] fileBytes = response.getBody();     // 👉 원본 Content-Disposition 헤더에서 파일 이름 추출     String disposition = response.getHeaders().getFirst(HttpHeaders.CONTENT_DISPOSITION);     String filename = "default.bin"; // fallback     if (disposition != null && disposition.contains("filename=")) {         // Content-Disposition: attachment; filename="some_file.bin"         filename = disposition.split("filename=")[1].replace("\"", "").trim();     }     HttpHeaders ...
Read more »

javascript cheatsheet

JavaScript 기능들을 정리한 치트시트를 제공합니다. 이 치트시트는 데이터 구조와 알고리즘을 구현하는 데 필요한 기본적인 구문과 기능을 포함하고 있습니다. ## JavaScript Coding Cheat Sheet ### 1. **기본 문법** #### 변수 선언 ```javascript let variable = value;   // 변수 선언 (변경 가능) const constant = value; // 상수 선언 (변경 불가) ``` #### 함수 선언 ```javascript // 함수 선언식 function functionName(params) {   // 함수 내용 } // 함수 표현식 const functionName = function(params) {   // 함수 내용 }; // 화살표 함수 const functionName = (params) => {   // 함수 내용 }; ``` ### 2. **기본 데이터 구조** #### 배열 (Array) ```javascript let arr = [1, 2, 3]; // 배열 길이 console.log(arr.length); // 배열 요소 접근 console.log(arr[0]); // 배열의 끝에 추가 arr.push(4); // 배열의 끝에서 제거 arr.pop(); // 배열의 앞에 추가 arr.unshift(0); // 배열의 앞에서 제거 arr.shift(); ``` #### 객체 (Object) ```javascript let obj = {   key1: 'value1',   key2: 'value2' }; // 속성 접근 console.log(obj.key1); // 속성 추가 또는 변경 obj.key3 = 'value3'; // 속성 제거 delete obj.key2; ``` ### 3. **반복문 및 조건문** #### 반복문 ```javascript // for 반복문 for (let i = 0; i ...
Read more »