Pagini recente » Cod sursa (job #1659103) | Cod sursa (job #3130270) | Cod sursa (job #651055) | Cod sursa (job #832482) | Cod sursa (job #250804)
Cod sursa(job #250804)
# include <cstdio>
# include <algorithm>
using namespace std;
# define FIN "infasuratoare.in"
# define FOUT "infasuratoare.out"
# define MAXN 120005
struct punct
{
double x, y;
} P[MAXN];
int N, i, p, vf;
int St[MAXN];
void swap(int i, int j)
{
punct aux;
aux = P[i]; P[i] = P[j]; P[j] = aux;
}
int cmp(punct A, punct B)
{
return (double) (A.x-P[1].x)*(B.y-P[1].y) > (double) (B.x-P[1].x)*(A.y-P[1].y);
}
int sign(int i, int j, int k)
{
double x1, y1;
x1 = (P[i].x - P[k].x) * (P[j].y - P[k].y);
y1 = (P[j].x - P[k].x) * (P[i].y - P[k].y);
if (x1 - y1 > 0) return 1;
return -1;
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&N);
for (i = 1, p = 1; i <= N; ++i)
{
scanf("%lf %lf",&P[i].x ,&P[i].y);
if (P[i].x < P[p].x) p = i;
if (P[i].x ==P[p].x && P[i].y < P[p].y) p = i;
}
swap(1,p);
sort(P + 2, P + N + 1, cmp);
St[vf = 1] = 1;
for (i = 2; i <= N; ++i)
{
while (vf >= 2 && sign(St[vf-1], St[vf], i) < 0) --vf;
St[++vf] = i;
}
printf("%d\n",vf);
for (i = 1; i <= vf; ++i)
printf("%lf %lf\n",P[St[i]].x, P[St[i]].y);
return 0;
}