Pagini recente » Borderou de evaluare (job #1635880) | Borderou de evaluare (job #2008641) | Profil santejudeandaiana | Cod sursa (job #1932239) | Cod sursa (job #410309)
Cod sursa(job #410309)
#include <cstdio>
#include <algorithm>
using namespace std;
#define file_in "infasuratoare.in"
#define file_out "infasuratoare.out"
#define Nmax 122121
int poz;
double x[Nmax];
double y[Nmax];
int n,i,k,st[Nmax],a[Nmax];
int cmp(int i, int j)
{
return (x[i]-x[poz])*(y[j]-y[poz])<(y[i]-y[poz])*(x[j]-x[poz]);
}
double aria(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]);
}
int main()
{
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &n);
for (i=1;i<=n;++i)
scanf("%lf %lf", &x[i], &y[i]);
//caut cel mai din stanga punct, iar in caz de egalitate cel mai de jos
poz=0;
x[poz]=10000000.0;
y[poz]=10000000.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;
//sortez in functie de panta dreptei
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 && aria(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]]);
fclose(stdin);
fclose(stdout);
return 0;
}