Pagini recente » Cod sursa (job #3031074) | Cod sursa (job #751216) | Cod sursa (job #3275204) | Cod sursa (job #1088771) | Cod sursa (job #3300578)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 120001
struct punct
{
float x, y;
};
int n;
int varf=0;
int vis[MAX];
int stiva[MAX];
int cmp(const void *a, const void *b) {
struct punct *p = (struct punct *)a;
struct punct *q = (struct punct *)b;
if (fabs(p->x - q->x) > 1e-8) return (p->x < q->x) ? -1 : 1;
if (fabs(p->y - q->y) > 1e-8) return (p->y < q->y) ? -1 : 1;
return 0;
}
void read(struct punct *space,FILE* fin)
{
for (int i = 0; i < n; i++)
{
fscanf(fin,"%f %f", &space[i].x, &space[i].y);
}
}
double crossproduct(struct punct a, struct punct b, struct punct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x -a.x);
}
void infasuratoare(struct punct *space, int n,FILE* fout)
{
qsort(space, n, sizeof(struct punct), cmp);
varf = 0;
for (int i = 0; i < n; i++) {
while (varf >= 2 && crossproduct(space[stiva[varf - 2]], space[stiva[varf - 1]], space[i]) <= 0) {
vis[stiva[--varf]] = 0;
}
stiva[varf++] = i;
vis[i] = 1;
}
int t = varf;
for (int i = n - 2; i >= 0; i--) {
if (vis[i]) continue;
while (varf > t && crossproduct(space[stiva[varf - 2]], space[stiva[varf - 1]], space[i]) <= 0) {
vis[stiva[--varf]] = 0;
}
stiva[varf++] = i;
vis[i] = 1;
}
fprintf(fout,"%d\n", varf);
for(int i=0;i<=varf-1;i++)
{
fprintf(fout,"%f %f\n", space[stiva[i]].x,space[stiva[i]].y);
}
}
int main()
{
FILE *fin,*fout;
fin= fopen("infasuratoare.in", "r");
fout= fopen("infasuratoare.out", "w");
fscanf(fin,"%d", &n);
struct punct space[n];
read(space,fin);
infasuratoare(space, n, fout);
}