#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define POINT_NUM 30


typedef struct tag_point
{
	double x, y;
}point_t;


int main(void)
{
	point_t point[POINT_NUM];
	double start_y, theta, theta2, theta_min, theta_prev;
	int i, j, start_index, theta_min_index, prev_index;

	for(i=0;i<POINT_NUM;i++)
	{
		point[i].x=(double)rand()/(RAND_MAX+1.0);
		point[i].y=(double)rand()/(RAND_MAX+1.0);
	}

	start_y=point[0].y;
	start_index=0;
	for(i=0;i<POINT_NUM;i++)
	{
		if(start_y>point[i].y)
		{
			start_y=point[i].y;
			start_index=i;
		}
	}
	printf("start_index=%d\n", start_index);

	for(i=0;i<POINT_NUM;i++)
	{
		printf("%f,%f\n", point[i].x, point[i].y);
	}

	printf("\n\n# 凸包構成\n# x, y, degree\n");
	prev_index=start_index;
	theta_prev=0.0;
	printf("%f,%f\n", point[start_index].x, point[start_index].y);
	for(i=0;i<POINT_NUM;i++)
	{
		int is_first=1;
		for(j=0;j<POINT_NUM;j++)
		{
			if(prev_index==j) continue;
			theta=atan2(point[j].y-point[prev_index].y, point[j].x-point[prev_index].x);
			theta2=theta-theta_prev;
			while(theta2>=2*M_PI) theta2-=2*M_PI;
			while(theta2<0.0) theta2+=2*M_PI;
			if(is_first || theta_min>theta2)
			{
				is_first=0;
				theta_min=theta2;
				theta_min_index=j;
			}
		}
		printf("%f,%f,%d\n", point[theta_min_index].x, point[theta_min_index].y, (int)(theta_min*180/M_PI));
		if(theta_min_index==start_index) break;
		prev_index=theta_min_index;
		theta_prev+=theta_min;
	}

	return 0;
}

start_index=28
0.840188,0.394383
0.783099,0.798440
0.911647,0.197551
0.335223,0.768230
0.277775,0.553970
0.477397,0.628871
0.364784,0.513401
0.952230,0.916195
0.635712,0.717297
0.141603,0.606969
0.016301,0.242887
0.137232,0.804177
0.156679,0.400944
0.129790,0.108809
0.998925,0.218257
0.512932,0.839112
0.612640,0.296032
0.637552,0.524287
0.493583,0.972775
0.292517,0.771358
0.526745,0.769914
0.400229,0.891529
0.283315,0.352458
0.807725,0.919026
0.069755,0.949327
0.525995,0.086056
0.192214,0.663227
0.890233,0.348893
0.064171,0.020023
0.457702,0.063096


# 凸包構成
# x, y, degree
0.064171,0.020023
0.457702,0.063096,6
0.998925,0.218257,9
0.952230,0.916195,77
0.493583,0.972775,79
0.069755,0.949327,10
0.016301,0.242887,82
0.064171,0.020023,16