Pagini recente » Cod sursa (job #2254297) | Cod sursa (job #658263) | Monitorul de evaluare | Cod sursa (job #1520551) | Cod sursa (job #2054783)
# 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> c,pair<long double,long double> d){
pair<long double,long double> a,b;
a=c;
b=d;
a.f-=xmin;
b.f-=xmin;
a.s-=ymin;
b.s-=ymin;
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;
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);
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;
}