Pagini recente » Cod sursa (job #1808398) | Istoria paginii runda/serj/clasament | Cod sursa (job #2701189) | Cod sursa (job #1467535) | Cod sursa (job #2054735)
# include <fstream>
# include <algorithm>
# include <iomanip>
# define DIM 120010
# define f first
# define s second
using namespace std;
const long double EPS=1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<long double,long double> v[DIM],rv[DIM];
int s[DIM],n,k,u,i,j,x,y;
long double xmin,ymin;
bool egal(int x){
return(x>=-EPS&&x<=EPS);
}
long double det(long double X1,long double Y1,long double X2,long double Y2,long double X3,long double Y3){
return (X2-X1)*(Y3-Y1)-(X3-X1)*(Y2-Y1);
}
bool cmp(pair<long double,long double> a,pair<long double,long double> b){
if(egal(a.f*b.s-a.s*b.f))
return (a.f*a.f+a.s*a.s)<(b.f*b.f+b.s*b.s);
return a.f*b.s>a.s*b.f;
}
int main () {
fin>>n;
for(i=1;i<=n;i++){
fin>>v[i].f>>v[i].s;
xmin=min(xmin,v[i].f);
ymin=min(ymin,v[i].s);
}
x=int(xmin);
y=int(ymin);
for(i=1;i<=n;i++){
if(x<0)
v[i].f-=x;
if(y<0)
v[i].s-=y;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++){
if(x<0)
v[i].f+=x;
if(y<0)
v[i].s+=y;
}
rv[++k]=v[n];
for(i=n;v[i].f*v[i-1].s==v[i].s*v[i-1].f&&i>1;i--)
rv[++k]=v[i-1];
for(i=k,j=n;i>=1;i--,j--)
v[j]=rv[i];
v[++n]=v[1];
for(i=1;i<=n;i++){
while(u>1&&det(v[s[u-1]].f,v[s[u-1]].s,v[s[u]].f,v[s[u]].s,v[i].f,v[i].s)<0)
u--;
s[++u]=i;
}
fout<<u-1<<"\n";
for(i=1;i<u;i++)
fout<<setprecision(6)<<fixed<<v[s[i]].f<<" "<<v[s[i]].s<<"\n";
return 0;
}