Lab Work #9
담당교수 : 정 진 우
실습조교 : 장 우 진
신 예 지
1. [code 제출] 점의 개수 N(<=100)을 입력받고, N개의 점의 좌표 X, Y를 입력받아 단순 다각형 Poly[]를 생성하는 프로그램을 아래의 소스 코드를 이용해 작성하시오. 또한 단순 다각형을 생성하는 과정에서 두 점사이의 상대각도 계산 횟수 및 각의 비교 횟수를 아래의 출력 예제에 맞춰 출력하시오. (단, 수평각들을 정렬하는 알고리즘은 Heap Sort를 이용하고, 점의 X,Y 좌표는 100보다 작다고 가정한다.) 1. [提交代码]使用下面的源代码并编写出 输入点的个数N（<= 100）的程序 并且输入N个点的坐标X和Y 并使用以下源代码生成一个简单的多边形Poly[] 的程序。 此外，在创建简单多边形的过程中，输出两点之间的相对角度计算次数 和 角的比较次数，像下面的输出示例一样进行输出。 （注意，对齐 水平角度的算法要使用Heap Sort，并假设 点X,Y的坐标小于100.） struct point { char c; int x, y; }; struct line { struct point p1, p2; }; struct point polygon[Nmax]; float ComputeAngle(struct point p1, struct point p2){ int dx, dy, ax, ay; float t; dx = p2.x - p1.x; ax = abs(dx); dy = p2.y - p1.y; ay = abs(dy); t = (ax+ay == 0) ? 0 : (float) dy/(ax+ay); if (dx < 0) t = 2-t; else if (dy < 0) t = 4+t; return t*90.0; } [입력 예제] [输入示例] 7 (N의 값) (N의 值) A 3 4 (점 A의 값) (点 A的值) B 1 2 (점 B의 값) (点 B的值) C 2 5 (점 C의 값) (点 C的值) D 2 6 (점 D의 값) (点 D的值) E 9 3 (점 E의 값) (点 E的值) F 5 3 (점 F의 값) (点 F的值) G 6 4 (점 G의 값) (点 G的值) H 8 7 (점 H의 값) (点 H的值) [출력 예제] [输出示例] 15 (수평각 계산 횟수) (水平角计算次数) 60 (각의 비교 횟수) (角的比较次数) (계산 횟수 및 비교 회수는 프로그램의 구조에 따라 동일한 알고리즘이라도 조금씩 달라질 수 있음) （计算次数和比较次数可以略有不同，取决于程序的结构，即使使用相同的算法） 2. [code 제출] 임의의 점 Z의 좌표값과 단순다각형 생성을 위한 N개의 점의 좌표값들을 입력받고, 해당 점이 단순 다각형Poly[] 내부에 존재하는 점인지 아닌지를 판단해주는 프로그램을 구현하시오. 이때, 아래의 입출력 예제에 맞춰 출력하시오. 2. [提交代码]做一个 输入任意点Z坐标和 用于创建一个简单的多边形的N个点的坐标的程序，并判断该点是否在多边形Poly[]内 的程序。 像下面的输出示例一样进行输出。 [입력 예제] [输入示例] 8 3 5 (N의 값, Z의 x좌표 값, Z의 y좌표 값) (N的值, Z的x坐标值, Z的y标值) A 3 4 (점 A의 값) (点 A的值) B 1 2 (점 B의 값) (点 B的值) C 2 5 (점 C의 값) (点 C的值) D 2 6 (점 D의 값) (点 D的值) E 9 3 (점 E의 값) (点 E的值) F 5 3 (점 F의 값) (点 F的值) G 6 4 (점 G의 값) (点 G的值) H 8 7 (점 H의 값) (点 H的值) [출력 예제] [输出示例] False (계산 횟수 및 비교 회수는 프로그램의 구조에 따라 동일한 알고리즘이라도 조금씩 달라질 수 있음) （计算次数和比较次数可以略有不同，取决于程序的结构，即使使用相同的算法） [보고서] 위의 각 문제 별 결과를 포함해 2쪽 이내의 보고서(소스코드는 실습 직후 별도 제출)를 작성하고 다음 실습시간 이전까지 eclass에 업로드하고 출력물을 제출하시오. 2019 Spring Computer Algorithm (01)