Pagini recente » Cod sursa (job #2838950) | Cod sursa (job #1963486) | Cod sursa (job #1587908) | Cod sursa (job #624146) | Cod sursa (job #764334)
Cod sursa(job #764334)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 120001
#define EPS 1e-12
struct point{ double x,y; }s[MAX],st[MAX],dr[MAX];
int n,n1,n2;
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.y * c.x - c.y * a.x - a.y * b.x; }
void subsets(){
st[0] = dr[0] = s[0];
n1 = n2 = 1;
for(int i=1;i<n-1;i++)
if( delta(s[0],s[n-1],s[i]) > 0 )st[n1++] = s[i]; else dr[n2++] = s[i];
st[n1++] = dr[n2++] = s[n-1];
}
void up_envelope(){
int n = 2;
for(int i=2;i<n1;i++)
{
while(n > 2 && delta(st[n-2],st[i],st[n-1]) - EPS < 0)n--;
st[n++] = st[i];
}
n1 = n;
}
void down_envelope(){
int n = 2;
for(int i=2;i<n2;i++)
{
while(n > 2 && delta(dr[n-2],dr[i],dr[n-1]) + EPS > 0)n--;
dr[n++] = dr[i];
}
n2 = 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_envelope();
down_envelope();
printf("%d\n",n1+n2-2);
for(int i=0;i<n1;i++)printf("%lf %lf\n",st[i].x,st[i].y);
for(int i=n2-2;i>0;i--)printf("%lf %lf\n",dr[i].x,dr[i].y);
// for(int i=0;i<n;i++)printf("%lf %lf\n",s[i].x,s[i].y);
// for(int i=0;i<n1;i++)printf("%lf %lf\n",st[i].x,st[i].y);
// for(int i=0;i<n1;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);
return 0;
}