Pagini recente » Cod sursa (job #2007109) | Cod sursa (job #893896) | Cod sursa (job #2054774)
# 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,poz;
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;
xmin=1000000001;
ymin=1000000001;
for(i=1;i<=n;i++){
fin>>v[i].f>>v[i].s;
if(v[i].f<xmin||(v[i].f==xmin&&v[i].s<ymin)){
xmin=v[i].f;
ymin=v[i].s;
poz=i;
}
}
for(i=1;i<=n;i++){
v[i].f-=xmin;
v[i].s-=ymin;
}
swap(v[1],v[poz]);
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++){
v[i].f+=xmin;
v[i].s+=ymin;
}
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;
}