알고리즘(Algorithm) 실습11

Posted by Patchman
2010.02.15 15:44 Univ Study/알고리즘과 실습


 

11-1. 다음에 주어진 프로그램을 참고해서 주어진 자료에 대한 단순 다각형을 결정하여 출력하는 프로그램을 완성하고 실습하시오. 또한, N(>30)개의 점을 randon() 함수로 발생하고, 이점들에 대한 단순다각형 Poly[]를 구하고, 이 과정에서 실행한 2점 사이의 수평각 계산 횟수와 각의 비교회수를 count해서 출력하시오. 단, 수평각들을 sort하는 알고리즘은 임의로 선택하고, x와 y좌표값은 100보다 작게 한다.

 

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

 

#define Nmax 40

 

// 점(point) 구조체

struct point

{

int x;

int y;

char c;

double angle;

};

 

// 선(line) 구조체

struct line

{

struct point p1;

struct point p2;

};

 

// Polygon Class

class Polygon

{

private :

 

int computeCount; // 수평각 계산회수

int compareCount; // 각의 비교회수

 

public :

 

Polygon(struct point *poly, int N); // Polygon 생성자

void printPoly(struct point *poly, int N); // 다각형 출력

void compute(struct point *poly, int N);

double ComputeAngle(struct point p1, struct point p2); // 수평각 계산

 

void insertion_sort(struct point *polygon, int N); // 삽입정렬

};

 

Polygon::Polygon(struct point *poly, int N)

{

computeCount=0; compareCount=0;

 

cout<<"----------------------------------------------\n\n";

 

printPoly(poly, N); // 수평각이 계산되기 전 점들 출력

compute(poly, N); // 수평각 계산

insertion_sort(poly, N); // 다각형의 angle 순으로 정렬

 

cout << "\n\n";

printPoly(poly, N); // 수평각이 계산된 후 정렬된 점들 출력

 

cout << "\n\n수평각 계산 회수 : ";

cout << computeCount << "\n";

cout << "각의 비교 회수 : ";

cout << compareCount << "\n\n";

 

cout<<"-----------------------------------------------\n\n";

}

 

void Polygon::printPoly(struct point *poly, int N)

{

int i;

for(i=1; i<=N; i++)

{

cout << poly[i].c << "[" << poly[i].x << "," << poly[i].y << "]" << " -> ";

}

cout << poly[1].c << "[" << poly[1].x << "," << poly[1].y << "]" << "\n";

}

 

void Polygon::compute(struct point *poly, int N)

{

int i, k=1;

for(i=1; i<N; i++) // 기준점 계산(Y축이 가장 작은 점)

{

if(poly[k].y > poly[i+1].y)

k = i+1;

}

for(i=1;i<=N;i++)

{

 

 

// 수평각 계산, angle에 정보를 저장

poly[i].angle = ComputeAngle(poly[k], poly[i]);

}

}

 

double Polygon::ComputeAngle(struct point p1, struct point p2)

{

int dx, dy, ax, ay;

double t;

 

computeCount++;

 

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 (double)t*90.0;

}

 

// 삽입정렬을 사용하여 다각형의 angle 순으로 정렬

void Polygon::insertion_sort(struct point *poly, int N)

{

int i,j;

struct point p;

for(i=2 ; i<=N ; i++)

{

p.angle = poly[i].angle;

p.c = poly[i].c;

p.x = poly[i].x;

p.y = poly[i].y;

 

j = i;

 

while (poly[j-1].angle > p.angle)

{

compareCount++; // 비교회수 카운트

 

poly[j].x = poly[j-1].x;

poly[j].y = poly[j-1].y;

poly[j].c = poly[j-1].c;

poly[j].angle = poly[j-1].angle;

j--;

}

 

compareCount++; // 비교회수 카운트

 

poly[j].angle = p.angle;

poly[j].c = p.c;

poly[j].x = p.x;

poly[j].y = p.y;

}

}

 

void main()

{

struct point poly1[] = { -1, -1, ' ', -1, // 0번 자리 초기화

1, 4, 'A', 0,

3, 2, 'B', 0,

2, 5, 'C', 0,

2, 6, 'D', 0,

9, 8, 'E', 0,

9, 3, 'F', 0,

5, 3, 'G', 0,

6, 4, 'H', 0,

8, 4, 'I', 0,

7, 1, 'J', 0};

 

cout<<"\n[ 주어진 자료 ]\n";

Polygon POLY1(poly1, 10);

 

struct point *poly2;

poly2 = new struct point[Nmax]; // Nmax 의 개수 만큼 point 생성

 

srand((int)time(NULL));

 

for(int i=1; i<=Nmax; i++)

{

poly2[i].x = rand()%100+1;

poly2[i].y = rand()%100+1;

poly2[i].c = i-1 + 'A';

poly2[i].angle = 0;

}

 

poly2[0].x = -1; poly2[0].y = -1; poly2[0].angle = -1; // 0번 자리 초기화

 

cout<<"\n\n[ Random" << "(" << Nmax << ") ]\n";

Polygon POLY2(poly2, Nmax);

 

}

 

▣ 결과 출력

 


'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습12  (0) 2010.02.15
알고리즘(Algorithm) 실습11  (0) 2010.02.15
알고리즘(Algorithm) 실습10  (0) 2010.02.15
알고리즘(Algorithm) 실습8  (0) 2010.02.15
알고리즘(Algorithm) 실습7  (0) 2010.02.15
알고리즘(Algorithm) 실습6  (0) 2010.02.15