티스토리 뷰
https://www.acmicpc.net/problem/11758
11758번: CCW
첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.
www.acmicpc.net
처음에는 1번점과 2번점으로 직선의 방정식을 구하고,
3번점의 x좌표를 대입했을때의 y값이 주어진 3번점의 y값과 같다면 평행, 위에 있다면 반시계, 아래있다면 시계 이런식으로 판단해봤다.
이 방법은 기울기를 구할때 나누기 연산이 수행되 부동소수점 오차 때문에 실패했다.
앱실론을 정하고 오차 비교도 해봤는데 여전히 실패.
다음 방법은 1번점,2번점의 기울기와, 1번점,3번점의 기울기의 대소를 비교했다.
이때 점1점2 기울기의 공식은 (y2-y1) / (x2-x1)
점1점3 기울기의 공식은 (y3-y1) / (x3-x1) 이고, 대소만 비교하면 되므로 분모의 곱을 각각 곱해서 비교해줬다.
답을 봤는데 ccw라는 알고리즘이 따로 있었다.
(https://tose33.tistory.com/537)
'PS' 카테고리의 다른 글
| 백준 2166. 다각형의 면적 (0) | 2022.02.24 |
|---|---|
| 백준 17386. 선분 교차 1 (0) | 2022.02.24 |
| 백준 1011. Fly me to the Alpha Centauri (0) | 2022.02.24 |
| 프로그래머스. 자동완성 (0) | 2022.02.22 |
| 백준 1913. 달팽이 (0) | 2022.02.19 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Spring
- binary search
- CSS
- Stack
- db
- BFS
- back tracking
- Unity
- Python
- C++
- DP
- Brute Force
- 자료구조
- graph
- 조합
- floyd warshall
- two pointer
- permutation
- 이분탐색
- recursion
- Implementation
- Tree
- priority queue
- greedy
- dfs
- Dijkstra
- MVC
- 재귀
- Kruskal
- C
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
글 보관함