Pagini recente » Cod sursa (job #1007508) | Cod sursa (job #1797637) | Cod sursa (job #1776646) | Cod sursa (job #326976) | Cod sursa (job #1794736)
# include <fstream>
# include <algorithm>
# include <iomanip>
# include <cmath>
# define DIM 120010
# define f first
# define s second
# define p pair<long double,long double>
# define INF 1000000010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
p v[DIM],s[DIM],z;
int n,k,i,poz;
long double xm,ym;
long double dist(p a){
return a.f*a.f+a.s*a.s;
}
long double det(p z,p a,p b){
return (a.f-z.f)*(b.s-z.s)-(b.f-z.f)*(a.s-z.s);
}
bool cmp(p a,p b){
if(det(z,a,b)==0)
return dist(a)<dist(b);
return det(z,a,b)>0;
}
int main () {
fin>>n;
z=make_pair(0,0);
xm=ym=INF;
for(i=1;i<=n;i++){
fin>>v[i].f>>v[i].s;
if(v[i].s<ym||(v[i].s==ym&&v[i].f<xm)){
xm=v[i].f;
ym=v[i].s;
poz=i;
}
}
swap(v[poz],v[1]);
for(i=1;i<=n;i++){
v[i].f-=xm;
v[i].s-=ym;
}
sort(v+2,v+n+1,cmp);
s[++k]=v[1];
s[++k]=v[2];
for(i=3;i<=n;i++){
while(det(s[k-1],s[k],v[i])<0)
k--;
s[++k]=v[i];
}
fout<<k<<"\n";
for(i=1;i<=k;i++)
fout<<setprecision(13)<<fixed<<s[i].f+xm<<" "<<setprecision(13)<<fixed<<s[i].s+ym<<"\n";
return 0;
}