Pagini recente » Cod sursa (job #2255669) | Rating Cosmin Onofre (cosminonofre) | Cod sursa (job #2091299) | Profil StarGold2 | Cod sursa (job #3301020)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
double x, y;
} Point_t;
int comparePoints(const void *a, const void *b) {
Point_t *p1 = (Point_t *)a;
Point_t *p2 = (Point_t *)b;
if(p1->x != p2->x) {
return (p1->x < p2->x) ? -1 : 1;
}
if(p1->y != p2->y) {
return (p1->y < p2->y) ? -1 : 1;
}
return 0;
}
double checkDirection(Point_t a, Point_t b, Point_t c) { //Cross product (>0 = left; 0 = collinear; <0 = right)
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int findShape(Point_t *points, int n, Point_t **finalShape) {
qsort(points, n, sizeof(Point_t), comparePoints); //Sort points with respect to x and then, after y
Point_t *shape = (Point_t *)malloc(2*n*sizeof(Point_t));
int k = 0;
//Lower shape
for(int i=0;i<n;i++) {
while(k >= 2 && checkDirection(shape[k-2], shape[k-1], points[i]) <= 0) {
k--;
}
shape[k++] = points[i];
}
//Upper shape
int t = k+1;
for(int i=n-2;i>-1;i--) {
while(k >= t && checkDirection(shape[k-2], shape[k-1], points[i]) <= 0) {
k--;
}
shape[k++] = points[i];
}
k--;
*finalShape = shape;
return k; //Shape size
}
int main() {
FILE *input, *output;
input = fopen("infasuratoare.in", "r");
output = fopen("infasuratoare.out", "w");
int n;
fscanf(input, "%d", &n);
Point_t *points = (Point_t *)malloc(n*sizeof(Point_t));
Point_t *shape;
for(int i=0;i<n;i++) {
fscanf(input, "%lf %lf", &points[i].x, &points[i].y);
}
int k = findShape(points, n, &shape);
fprintf(output, "%d\n", k);
for(int i=0;i<k;i++) {
fprintf(output, "%.6lf %.6lf\n", shape[i].x, shape[i].y);
}
free(points);
free(shape);
fclose(input);
fclose(output);
return 0;
}