Pagini recente » Cod sursa (job #2147630) | Cod sursa (job #2245833) | Cod sursa (job #2739397) | Cod sursa (job #2814430) | Cod sursa (job #2776226)
#include<fstream>
#include<iomanip>
using namespace std;
ifstream F("infasuratoare.in");
ofstream G("infasuratoare.out");
#define N 120001
int n,p,i,t,s[N];
struct P {
double x,y;
};
P v[N],r,u[N];
#define A(a,b,c) ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))
void M(int l,int r)
{
if(l==r)
return;
int i,j,k,m=(l+r)/2;
for(M(l,m),M(m+1,r),i=k=l,j=m+1;i<=m||j<=r;)
u[k++]=(j>r||(i<=m&&A(v[1],v[i],v[j])<0))?v[i++]:v[j++];
for(i=l;i<=r;++i)
v[i]=u[i];
}
int main()
{
F>>n;
for(p=i=1;i<=n;++i)
F>>v[i].x>>v[i].y,p=v[i].x<v[p].x||(v[i].x==v[p].x&&v[i].y<v[p].y)?i:p;
for(r=v[1],v[1]=v[p],v[p]=r,M(2,n),s[++t]=1,i=2;i<=n;++i) {
for(;t>1&&A(v[s[t-1]],v[s[t]],v[i])>0;--t);
s[++t]=i;
}
for(G<<t<<"\n";t;--t)
G<<setprecision(6)<<fixed<<v[s[t]].x<<" "<<v[s[t]].y<<"\n";
return 0;
}