[UVa - 10135] Herding Frosh

Problem

One day, a lawn in the centre of campus became infested with Frosh. In an effort to beautify the campus, one of our illustrious senior classmen decided to round them up using a length of pink silk. Your job is to compute how much silk was required to complete the task. The senior classman tied the silk to a telephone post, and walked around the perimeter of the area containing the Frosh, drawing the silk taught so as to encircle all of them. He then returned to the telephone post. The senior classman used the minimum amount of silk necessary to encircle all the frosh plus one extra metre at each end to tie it. You may assume that the telephone post is at coordinates (0,0), where the first dimension is North/South and the second dimension is East/West. The coordinates of the Frosh are given in metres relative to the post. There are no more than 1000 Frosh.

 

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input consists of a line specifying the number of Frosh, followed by one line per Frosh with two real numbers his or her position.

 

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output consists of a single number - the length of silk in metres, to two decimal places.

 

Sample Input

1

 

4

1.0 1.0

-1.0 1.0

-1.0 -1.0

1.0 -1.0 

Sample Output

10.83

 

#define _CRT_SECURE_NO_WARNINGS
#define MAX 100
#define NUMBER_OF_FILES 5
#define STACK_SIZE 100
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point {
	int name;
	float x;
	float y;
	float tan;
}point[100];


int stack[STACK_SIZE];    // 스택
int top = -1;
double t_dist;
float silk[10];

int isFull() {
	if (top >= STACK_SIZE - 1) {    // stack의 인덱스 0부터 시작
		printf("Error : Stack is Full!\n");
		return 1;
	}
	return 0;
}

int isEmpty() {
	if (top == -1) {
		printf("Error : Stack is empty!\n");
		return 1;
	}
	return 0;
}

void push(int data) {
	//printf("push : %d\n", data);
	if (!isFull()) {
		top++;
		stack[top] = data;
	}
}

int pop() {
	//printf("pop\n");
	if (!isEmpty()) {
		return stack[top--];
	}
}

void printStack() {
	int i;
	for (i = 0; i <= top; i++) {
		printf("%d ", stack[i]);
	}
	printf("\n");
}


int ccw(int p1, int p2, int p3) {
	printf("\n");
	//printf("p1.x : %.2f  p1.y : %.2f / p2.x : %.2f  p2.y : %.2f / p3.x : %.2f  p3.y : %.2f\n", point[p1].x, point[p1].y, point[p2].x, point[p2].y, point[p3].x, point[p3].y);
	return (point[p2].x - point[p1].x) * (point[p3].y - point[p1].y) - (point[p3].x - point[p1].x) * (point[p2].y - point[p1].y);
}

void swap(struct Point* arr, int a, int b)
{
	//한 배열이 뭉탱이로 옮겨짐.(정보갱신)
	struct Point temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void sort(int size, int min_y) {
	float min_t = MAX;
	float t = 0;
	//printf("init : %d, %f, %f, %f\n", point[min_y].name, point[min_y].x, point[min_y].y, point[min_y].tan);
	for (int i = 1; i <= size + 1; i++) {
		if (i == min_y)
			point[i].tan = -1;
		else if (point[i].x - point[min_y].x == 0)
			point[i].tan = MAX;
		else if ((point[i].x - point[min_y].x) < 0) {
			t = fabs((point[i].y - point[min_y].y) / (point[i].x - point[min_y].x));
			point[i].tan = t + 100 + 10/t;
		}
		else
			point[i].tan = fabs((point[i].y - point[min_y].y) / (point[i].x - point[min_y].x));
	}
	for (int i = 1; i <= size; i++) {
		//printf("%d %f\n", point[i].name, point[i].tan);
	}

	//정렬
	for (int i = 1; i <= size; i++) {
		for (int j = 1; j <= size - i; j++) {
			if (point[j + 1].tan < point[j].tan) {
				swap(point, j + 1, j);
			}
		}
		//printf("\n");
	}
}

double distance(float x1, float y1, float x2, float y2) {
	//printf("%f\n", sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

void Algorithm(int n, int size) {
	int stack_size, insert = 0, count = 0;
	int res_arr[20];
	for (int i = 0; i <= size; i++) {
		//printf("%d %f\n", point[i].name, point[i].tan);
	}
	push(1);
	push(2);
	int next = 3;
	int index = 1;
	// 다음 넣을 점
	while (next <= size)
		// convex hull 만들기
	{
		if (next == size && point[next - 1].x < point[next].x && point[next - 1].y > point[next].y)
			break;

		while (1)
		{
			int first, second;
			second = stack[index--];
			pop();
			first = stack[index];
			//printf("first : %d second : %d next : %d\n", first, second, next);
			if (ccw(first, second, next) > 0) {
				push(second);
				break;
			}
		}
		index += 2;
		push(next++);
		//printStack();	
	}
	for (int i = 0; i < 20; i++) {
		res_arr[i] = 0;
	}
	for (int i = 0; i < top + 1; i++) {
		if (stack[i] > 0) {
			res_arr[i] = stack[i];
			count++;
		}
	}
	if (ccw(stack[0], stack[top - 1], stack[top]) == 0) {
		pop();

	}
	printf("count : %d\n", count);
	printf("result : ");
	for (int i = 0; i < top + 1; i++) {
		printf("%d ", res_arr[i]);
		if (res_arr[i] > 0)
			count++;
	}
	printf("\n\n\n");
	for (int i = 0; i < top; i++) {
		//printf("%d) x1 : %.2f / y1 : %.2f \nx2 : %.2f / y2 : %.2f\n", res_arr[i], point[res_arr[i]].x, point[res_arr[i]].y, point[res_arr[i + 1]].x, point[res_arr[i + 1]].y);
		t_dist += distance(point[res_arr[i]].x, point[res_arr[i]].y, point[res_arr[i + 1]].x, point[res_arr[i + 1]].y);
	}
	printf("x1 : %.2f / y1 : %.2f \nx2 : %.2f / y2 : %.2f\n", point[res_arr[top]].x, point[res_arr[top]].y, point[res_arr[0]].x, point[res_arr[0]].y);
	if (!(point[res_arr[0]].x == point[res_arr[top]].x && point[res_arr[0]].y == point[res_arr[top]].y)) {
		t_dist += distance(point[res_arr[top]].x, point[res_arr[top]].y, point[res_arr[0]].x, point[res_arr[0]].y);
	}
		
	printf("distance : %f\n", t_dist);
	float min = MAX;
	for (int i = 0; i <= top; i++) {
		if (distance(point[res_arr[i]].x, point[res_arr[i]].y, 0, 0) < min)
			min = distance(point[res_arr[i]].x, point[res_arr[i]].y, 0, 0);
	}
	printf("min : %f\n", min);
	t_dist += 2 * min;
	printf("total distance : %f\n", t_dist);
	silk[n] = t_dist;
	t_dist = 0;
}



int minimum(int size) {
	int min_y = 0, y = MAX;
	for (int i = 1; i <= size; i++) {
		if (point[i].y < y) {
			y = point[i].y;
			min_y = i;
		}

	}
	return min_y;
}


int File_input(int i) {
	char Input[5][15] = {
		"Input_1.txt", "Input_2.txt", "Input_3.txt", "Input_4.txt", "Input_5.txt"
	};

	FILE* input;
	input = fopen(Input[i], "r");

	int set = 0, points = 0, min_y = MAX;
	double d = 0, y = MAX, min_d = MAX;

	if (input != NULL) {
		int a = fscanf(input, "%d", &set);
		for (int n = 0; n < set; n++) {
			a = fscanf(input, "%d", &points);
			for (int i = 1; i <= points; i++) {
				point[i].name = i;
				a = fscanf(input, "%f %f", &point[i].x, &point[i].y);
				printf("%d %.2f %.2f\n", point[i].name, point[i].x, point[i].y);
			}
			min_y = minimum(points);
			printf("min_y : %d\n", min_y);
			sort(points, min_y);
			Algorithm(n, points);
			printf("min dist : %f\n", min_d);
			printStack();
			top = -1;
			printf("\n\n\n");
		}
	}
	else {
		printf("Error.");
		exit(1);
	}

	fclose(input);
	return set;
}

void File_output(int i) {
	char Output[5][15] = {
		"Output_1.txt", "Output_2.txt", "Output_3.txt", "Output_4.txt", "Output_5.txt"
	};

	FILE* output;
	output = fopen(Output[i], "a");

	if (output != NULL) {
		for (int i = 0; i < 10; i++) {
			if(silk[i] > 0)
				fprintf(output, "%.2f\n\n", silk[i]);
		}
		for (int i = 0; i < 10; i++)
			silk[i] = 0;
	}
	else {
		printf("Error.");
		exit(1);
	}

	fclose(output);
}

int main(void) {
	int n = 0;
	for (int i = 0; i < NUMBER_OF_FILES; i++) {
		File_input(i);
		File_output(i);
	}
}