[컴퓨터공학] VC 6.0으로 구현한 OOP기반의 Convex hull
- 최초 등록일
- 2003.11.13
- 최종 저작일
- 2003.11
- 11페이지/ 한컴오피스
- 가격 3,000원
소개글
연세대 프로그래밍 실습과목에서 레포트점수 만점 받은 레포트 입니다. 대략 도서관에서 하루 밤샌 결과물입니다 ^^; 물론 본문에 소스코드에 주석 삽입하여 설명하였습니다.
목차
Program Specification
How to compile and execute
Algorithm and Data Structure
1. 각도 계산 알고리즘
2. CCW (세 점의 방향성 검사)
3. Graham Algorithm(Convex hull을 O(nlogn)의 시간복잡도로 구할 수 있는 현재까지 알려진 최적의 해법)
Anchor (PS[1]) 구하기
각도 정렬하기
Stack 작업 - Convex hull 집합 구하기
4. Convex hull의 출력
Future Work
본문내용
Program Specification
이번 HW#2는 C++의 강력한 OOP를 이용한 체계적인 구조를 갖는 데이터 형을 제작하여, Built-in 데이터 형이 아닌 새로 만든 데이터 형을 이용하여 프로그램을 구현하는 것이다. 프로그램의 목적은 “Convex Hull" 프로그램을 구현하는것인데, 사용된 알고리즘은 CCW (세 점의 방향성 판별), 두 점을 잇는 선분의 각도를 제는 알고리즘, 그리고 정렬에 사용된 선택 정렬, 마지막으로 과제의 MAIN-알고리즘인 Graham 알고리즘이 있다. 사용된 데이터-구조로는 Graham 알고리즘에서 사용된 스택이 있는데, 이는 배열을 이용하여 구현하였다.
How to compile and execute
COMPILER : MS Visual C++ 6.0
About warning and special comment : 특별히 warning message는 없다.
USER MANUAL :
실행 폴더에 input.txt 파일을 만든 후, input.txt에는 다음과 같은 형식으로 N개의 좌표에 대한 정보를 입력한다.
N
P1.x P1.y
P2.x P2.y
.
.
PN.x PN.y
출력 파일의 이름은 test.ps 이다. 파일에는 주어진 입력에 대한 convex hull과 좌표들이 visual하게 출력될 것이다.
참고 자료
없음