Pagini recente » Cod sursa (job #1432643) | Cod sursa (job #2057467) | Monitorul de evaluare | Cod sursa (job #1737645) | Cod sursa (job #767513)
Cod sursa(job #767513)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 120002
#define EPS 1e-12
struct punct{ long double x,y; }s[MAX],st[MAX],dr[MAX];
int n,n_st,n_dr;
bool sort_mode(punct a,punct b){ return a.x < b.x; }
long double delta(punct a,punct b,punct c){
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
void subsets(){
st[0] = dr[0] = s[0];
for(int i=1;i<n-1;i++)
if( delta( s[0], s[n-1], s[i] ) > 0 ) st[++n_st] = s[i]; else dr[++n_dr] = s[i];
st[++n_st] = dr[++n_dr] = s[n-1];
n_st ++;
n_dr ++;
}
void up_subset(){
int n = 2;
for(int i=2;i<n_st-1;i++)
{
while( n >= 2 && delta( st[n-2], st[i], st[n-1] ) + EPS < 0 )n--;
st[n++] = st[i];
}
st[n++] = st[n_st-1];
n_st = n;
}
void down_subset(){
int n = 2;
for(int i=2;i<n_dr-1;i++)
{
while( n >= 2 && delta( dr[n-2], dr[i], dr[n-1] ) - EPS > 0 )n--;
dr[n++] = dr[i];
}
dr[n++] = dr[n_dr-1];
n_dr = n;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%llf %llf",&s[i].x,&s[i].y);
sort(s,s+n,sort_mode);
subsets();
up_subset();
down_subset();
printf("%d\n",n_st+n_dr-2);
for(int i=n_st-1;i>=0;i--)printf("%llf %llf\n",st[i].x,st[i].y);
for(int i=1;i<n_dr-1;i++)printf("%llf %llf\n",dr[i].x,dr[i].y);
// for(int i=0;i<n_dr;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);
return 0;
}