Pagini recente » Cod sursa (job #1279524) | Cod sursa (job #2056959) | Cod sursa (job #2856983) | Cod sursa (job #2476912) | Cod sursa (job #477052)
Cod sursa(job #477052)
#include <cstdio>
#include <algorithm>
using namespace std;
#define file_in "infasuratoare.in"
#define file_out "infasuratoare.out"
#define nmax 123234
int n;
double x[nmax];
double y[nmax];
int poz;
int st[nmax];
int a[nmax];
void citire()
{
freopen(file_in,"r",stdin);
freopen(file_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 arie(int a, int b, int c)
{
return (x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[b]*x[c]-x[a]*y[c]-y[a]*x[b]);
}
void solve()
{
int i,k;
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)
a[++a[0]]=i;
sort(a+1,a+a[0]+1,cmp);
k=0;
st[++k]=poz;
st[++k]=a[0];
for (i=1;i<=a[0];++i)
{
while(k>1 && arie(st[k-1],st[k],a[i])>0) k--;
st[++k]=a[i];
}
printf("%d\n", k);
for(i=k;i>=1;--i)
printf("%.6lf %.6lf\n", x[st[i]],y[st[i]]);
}
int main()
{
citire();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}