Pagini recente » Cod sursa (job #1430822) | Cod sursa (job #631998) | Cod sursa (job #3187881) | Cod sursa (job #1742413) | Cod sursa (job #527986)
Cod sursa(job #527986)
#include <stdio.h>
#include <algorithm>
#define nmax 999999
using namespace std;
int n;
double x[nmax];
double y[nmax];
int poz, S[nmax], P[nmax];
void citire()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for (int i=1;i<=n;++i)
scanf("%lf %lf", &x[i], &y[i]);
}
int cmp(int i, int j)
{
return (x[i]-x[poz])*(y[j]-y[poz])<(y[i]-y[poz])*(x[j]-x[poz]);
}
double produs(int a, int b, int c)
{
return ((x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]));
}
void solve()
{
int i,varf;
poz=0;
x[poz]=1000000.0;
y[poz]=1000000.0;
for (i=1;i<=n;++i)
if ((x[i]<x[poz]) || (x[i]==x[poz] && y[i]<y[poz]))
poz=i;
for (i=1;i<=n;++i)
if (i!=poz)
P[++P[0]]=i;
sort(P+1,P+P[0]+1,cmp);
varf=0;
S[++varf]=poz;
S[++varf]=P[0];
for (i=1;i<=P[0];++i)
{
while(varf>1 && produs(S[varf-1],S[varf],P[i])>0) varf--;
S[++varf]=P[i];
}
printf("%d\n", varf);
for(i=varf;i>=1;--i)
printf("%.6lf %.6lf\n", x[S[i]],y[S[i]]);
}
int main()
{
citire();
solve();
return 0;
}