Pagini recente » Cod sursa (job #37513) | Cod sursa (job #1653866) | Cod sursa (job #1482494) | Cod sursa (job #2356709) | Cod sursa (job #729423)
Cod sursa(job #729423)
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int N,i,p,m,vect[120002];
struct nod
{
double x,y;
double unghi;
};
nod a[120002],aux;
double x,y,ip,l1,l2,min1;
bool cmp1(nod a,nod b)
{
if (a.unghi>b.unghi) return 1;
else return 0;
}
bool intoarcere(int x,int y,int z)
{
double a1,b1,c1,s;
a1=a[x].y-a[y].y;
b1=a[y].x-a[x].x;
c1=a[x].x*a[y].y-a[y].x*a[x].y;
s=a1*a[z].x+b1*a[z].y+c1;
if (s<=0) return 1;
else return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
min1=10000;
for (i=1;i<=N;i++)
if (a[i].y<min1)
{
min1=a[i].y;
p=i;
}
else
if (a[i].y==min1&&a[i].x<a[p].x)
p=i;
aux=a[1];
a[1]=a[p];
a[p]=aux;
for (i=2;i<=N;i++)
{
l1=1.0*(a[i].y-a[1].y);
l2=1.0*(a[i].x-a[1].x);
ip=sqrt(l1*l1+l2*l2);
a[i].unghi=l2/ip;
}
sort(a+2,a+N+1,cmp1);
m=3;
vect[1]=1;
vect[2]=2;
vect[3]=3;
for (i=4;i<=N;i++)
{
while (intoarcere(vect[m-1],vect[m],i)&&m>2)
m--;
m++;
vect[m]=i;
}
printf("%d\n",m);
for (i=1;i<=m;i++)
printf("%.6lf %.6lf\n",a[vect[i]].x,a[vect[i]].y);
return 0;
}