Pagini recente » Cod sursa (job #3277520) | Cod sursa (job #1932923) | Cod sursa (job #569260) | Cod sursa (job #2522153) | Cod sursa (job #272408)
Cod sursa(job #272408)
#include<stdio.h>
#include<stdlib.h>
#define N_MAX 128000
struct point
{
double x, y;
} v[N_MAX];
int cmp(const void *A, const void*B)
{
point *a, *b;
a=(point *)A;
b=(point *)B;
if (a->x > b->x)
return 1;
if ((a->x == b->x) && (a->y > b->y ))
return 1;
return -1;
}
int q(int a, int b, int c)
{
double det= v[c].x * (v[a].y-v[b].y) + v[c].y * (v[b].x-v[a].x) +v[a].x * v[b].y - v[b].x *v[a].y;
if (det < 0) return 1;
return 0;
}
int st[N_MAX], dr[N_MAX], stn, drn;
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
//freopen("date.in", "r", stdin);
//freopen("date.out", "w", stdout);
int n, i;
scanf("%d", &n);
for (i=1;i<=n; i++)
scanf("%lf %lf", &(v[i].x), &(v[i].y));
qsort(&v[1], n, sizeof(point), cmp);
st[1]=1;
st[2]=2;
dr[1]=1;
dr[2]=2;
stn=2;
drn=2;
for (i=3; i<=n; i++)
{
stn++;
drn++;
st[stn]=i;
dr[drn]=i;
while (q(st[stn-2], st[stn-1], st[stn])&& (stn>=3))
{
stn--;
st[stn]=st[stn+1];
}
while((!q(dr[drn-2], dr[drn-1], dr[drn])) && (drn>=3))
{
drn--;
dr[drn]=dr[drn+1];
}
}
for (i=drn-1; i>1; i--)
{
++stn;
st[stn]=dr[i];
}
printf("%d\n", stn);
for (i=1; i<=stn; i++)
{
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
}
fclose(stdout);
return 0;
}