Pagini recente » Cod sursa (job #2097651) | Cod sursa (job #2097659) | Cod sursa (job #2417451) | Cod sursa (job #3357295) | Cod sursa (job #3359133)
#include <stdio.h>
#include <stdlib.h>
#define EPS 1e-12
typedef struct
{
double x, y;
} Point;
Point P[120005];
Point H[240005];
int cmp(const void *a, const void *b)
{
Point *p1 = (Point *)a;
Point *p2 = (Point *)b;
if(p1->x < p2->x){
return -1;
}
if(p1->x > p2->x){
return 1;
}
if(p1->y < p2->y){
return -1;
}
if(p1->y > p2->y){
return 1;
}
return 0;
}
double cross_product(Point o, Point a, Point b)
{
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
int main(void)
{
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
int n, i, k = 0, t;
fscanf(fin, "%d", &n);
for(i = 0; i < n; i++){
fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
}
qsort(P, n, sizeof(Point), cmp);
for(i = 0; i < n; i++){
while(k >= 2 && cross_product(H[k - 2], H[k - 1], P[i]) <= EPS){
k--;
}
H[k++] = P[i];
}
t = k + 1;
for(i = n - 2; i >= 0; i--){
while(k >= t && cross_product(H[k - 2], H[k - 1], P[i]) <= EPS){
k--;
}
H[k++] = P[i];
}
k--;
int min_idx = 0;
for(i = 1; i < k; i++){
if(H[i].y < H[min_idx].y || (H[i].y == H[min_idx].y && H[i].x < H[min_idx].x)){
min_idx = i;
}
}
fprintf(fout, "%d\n", k);
for(i = 0; i < k; i++){
int idx = (min_idx + i) % k;
fprintf(fout, "%.6lf %.6lf\n", H[idx].x, H[idx].y);
}
fclose(fin);
fclose(fout);
return 0;
}