Cod sursa(job #605099)
#include <iostream>
#include <iomanip>
#include <fstream>
#define DN 120005
using namespace std;
int n,ind[DN],stk[DN],p;
double x[DN],y[DN];
bool det(int i1, int i2,int i3) {
return(x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-
y[i1]*x[i2]-y[i2]*x[i3]-y[i3]*x[i1]
)<=0;
}
bool cmp(int a, int b) {
return (y[a]-y[p])*(x[b]-x[p])<(y[b]-y[p])*(x[a]-x[p]);
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(int i=1; i<=n; ++i) {
f>>x[i]>>y[i];
ind[i]=i;
}
int sz;
p=1;
sort(ind+1,ind+n+1,cmp);
stk[++sz]=1;
for(int i=1; i<=n; ++i) {
for(;sz>=2 && det(stk[sz-1],stk[sz],ind[i]);--sz);
stk[++sz]=ind[i];
}
for(int i=1; i<=sz; ++i) g<<fixed<<setprecision(6)<<x[stk[i]]<<' '<<y[stk[i]]<<'\n';
return 0;
}