Polar Angles
A point (x,y), on the cartesian plane, makes an angle theta with the positive direction of the x-axis. Theta varies in the interval [0 ,2PI) radians, i.e, greater than or equal to zero; but less than 2*PI radians.
For example, the polar angle of the point (1,2) as marked in this plane below, is (approximately) 63.4 degrees (multiply by PI/180 to convert to radians)
Ref http://eldar.mathstat.uoguelph.ca/dashlock/Outreach/Articles/images/PRfig1.jpg
The Task
Given a list of points in the 2D plane, sort them in ascending order of their polar angle. In case multiple points share exactly the same polar angle, the one with lesser distance from the origin (0,0) should occur earlier in the sorted list.
Input Format
The first line contains an integer N.
This is followed by N lines containing pairs of space separated integers, x and y which represent the coordinates of the points in the cartesian plane.
Constraints
1 <= N <= 1000
-100 <= x,y <= 100
The point (0,0) will not be present in the list of points.
Output Format
The output should contain N lines.
Each line should contain two integers x and y, corresponding to a point in the original list. Display the points in ascending order of their polar angle.
Sample Input
4
1 0
0 -1
-1 0
0 1
Sample Output
1 0
0 1
-1 0
0 -1
Explanation
The point (0,1) has a polar angle of 90 degrees. The point (1,0) has a polar angle of 0 degrees. (-1,0) has a polar angle of 180 degrees and (0,-1) has a polar angle of 270 degrees.
xxxxxxxxxx
char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);
int parse_int(char*);
/*
* Complete the 'solve' function below.
*
* The function is expected to return a 2D_INTEGER_ARRAY.
* The function accepts 2D_INTEGER_ARRAY coordinates as parameter.
*/
/*
* To return the 2d integer array from the function, you should:
* - Store the number of rows of the array to be returned in the result_rows variable
* - Store the number of columns of the array to be returned in the result_columns variable
* - Allocate the array dynamically
*
* For example,
* int** return_2d_integer_array(int* result_rows, int* result_columns) {
* *result_rows = 2;
* *result_columns = 3;
*
* int** a = malloc(2 * sizeof(int*));
*
* for (int i = 0; i < 2; i++) {
* *(a + i) = malloc(3 * sizeof(int));
*
* for (int j = 0; j < 3; j++) {
* *(*(a + i) + j) = 3 * i + j + 1;
* }
* }
*
* return a;
* }
*
*/
int** solve(int coordinates_rows, int coordinates_columns, int** coordinates, int* result_rows, int* result_columns) {
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int n = parse_int(ltrim(rtrim(readline())));
int** coordinates = malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
*(coordinates + i) = malloc(2 * (sizeof(int)));
char** coordinates_item_temp = split_string(rtrim(readline()));
for (int j = 0; j < 2; j++) {
int coordinates_item = parse_int(*(coordinates_item_temp + j));
*(*(coordinates + i) + j) = coordinates_item;
}
}
int result_rows;
int result_columns;
int** result = solve(n, 2, coordinates, &result_rows, &result_columns);
for (int i = 0; i < result_rows; i++) {
for (int j = 0; j < result_columns; j++) {
fprintf(fptr, "%d", *(*(result + i) + j));
if (j != result_columns - 1) {
fprintf(fptr, " ");
}
}
if (i != result_rows - 1) {
fprintf(fptr, "\n");
}
}
fprintf(fptr, "\n");
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) {
break;
}
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
break;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
char* ltrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
while (*str != '\0' && isspace(*str)) {
str++;
}
return str;
}
char* rtrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
char* end = str + strlen(str) - 1;
while (end >= str && isspace(*end)) {
end--;
}
*(end + 1) = '\0';
return str;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
int parse_int(char* str) {
char* endptr;
int value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}