Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/vladv28 | Profil BlatTraditional | Atasamentele paginii sda | Cod sursa (job #788892)
Cod sursa(job #788892)
#include <cstdio>
#include <algorithm>
using namespace std;
#define Max 120001
#define Eps 1e-8
struct point{double x,y;}s[Max],s0[Max],s1[Max];
int n,n0,n1;
bool sort_type(point a,point b){return a.x<b.x;}
double delta(point a,point b,point c)
{return a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;}
void subsets()
{
s0[0]=s1[0]=s[0];
n0=n1=1;
for(int i=1;i<n-1;i++)
if(delta(s[0],s[n-1],s[i])>0)s0[n0++]=s[i]; else s1[n1++]=s[i];
s0[n0++]=s1[n1++]=s[n-1];
}
void up_subset()
{
n=2;
for(int i=2;i<n0-1;i++)
{
while(delta(s0[n-2],s0[i],s0[n-1]) + Eps < 0)n--;
s0[n++]=s0[i];
}
s0[n++]=s0[n0-1];
n0=n;
}
void down_subset()
{
n=2;
for(int i=2;i<n1-1;i++)
{
while(delta(s1[n-2],s1[i],s1[n-1]) - Eps > 0)n--;
s1[n++]=s1[i];
}
s1[n++]=s1[n1-1];
n1=n;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lf %lf",&s[i].x,&s[i].y);
sort(s,s+n,sort_type);
subsets();
up_subset();
down_subset();
printf("%d\n",n0+n1-2);
for(int i=n0-1;i>=0;i--)printf("%lf %lf\n",s0[i].x,s0[i].y);
for(int i=1;i<n1-1;i++)printf("%lf %lf\n",s1[i].x,s1[i].y);
// for(int i=0;i<n1;i++)printf("%lf %lf\n",s1[i].x,s1[i].y);
return 0;
}