Pagini recente » Cod sursa (job #1903090) | Cod sursa (job #2058730) | Cod sursa (job #1725530) | Cod sursa (job #1999859) | Cod sursa (job #536432)
Cod sursa(job #536432)
#include<stdio.h>
#include<algorithm>
#define NMAX 120010
#define err 1e-12
#define x first
#define y second
#define pdd pair<double,double>
using namespace std;
pair<double,double> pct[NMAX],sol[NMAX];
int n,i,stack[NMAX],MIN;
bool used[NMAX];
inline int cmp(double aa, double bb)
{
if(aa+err<bb) return -1;
if(bb+err<aa) return 1;
return 0;
}
inline int cmppdd(const pdd &a, const pdd &b)
{
int v=cmp(a.x,b.x);
if(v) return (v==-1);
return (cmp(a.y,b.y)==-1);
}
inline int semn(pdd a, pdd b, pdd c)
{
double aa=a.y - b.y, bb=b.x - a.x, cc=a.x*b.y - a.y*b.x;
return cmp(aa*c.x+bb*c.y+cc,0);
}
inline void pol()
{
int sens=1,nr_puncte=2;
stack[1] = 1; stack[2] = 2; used[2]= true;
i=3;
while(!used[1])
{
while(used[i])
{
if(i==n) sens = -sens;
i+= sens;
}
while(nr_puncte>=2 && semn(pct[stack[nr_puncte-1]], pct[stack[nr_puncte]], pct[i])==-1)
used[stack[nr_puncte--]] = false;
stack[++nr_puncte]=i;
used[i]=true;
}
MIN=nr_puncte-1;
for(i=1;i<=MIN;i++) sol[i]=pct[stack[i]];
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%lf %lf",&pct[i].x,&pct[i].y);
sort(pct+1,pct+n+1,cmppdd);
pol();
printf("%d\n",MIN);
for(i=1;i<=MIN;i++)
printf("%.6lf %.6lf\n",sol[i].x,sol[i].y);
return 0;
}