Pagini recente » Cod sursa (job #611262) | Cod sursa (job #2312717) | Cod sursa (job #290220) | Cod sursa (job #1890519) | Cod sursa (job #2196700)
# include <fstream>
# include <algorithm>
# include <cmath>
# include <iomanip>
# define DIM 120010
# define x first
# define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<long double,long double> v[DIM],sol[DIM],df;
int n,u,i;
long double dist(pair<long double,long double> a){
return sqrt(a.x*a.x+a.y*a.y);
}
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(det(0,0,a.x,a.y,b.x,b.y)==0)
return dist(a)<dist(b);
return det(0,0,a.x,a.y,b.x,b.y)<0;
}
int main () {
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1);
df=v[1];
for(i=n;i>=1;i--){
v[i].x-=v[1].x;
v[i].y-=v[1].y;
}
sort(v+2,v+n+1,cmp);
sol[++u]=v[1];
sol[++u]=v[2];
for(i=3;i<=n;i++){
while(det(sol[u-1].x,sol[u-1].y,sol[u].x,sol[u].y,v[i].x,v[i].y)>=0&&u>1)
u--;
sol[++u]=v[i];
}
fout<<u<<"\n";
for(i=u;i>=1;i--)
fout<<setprecision(6)<<fixed<<sol[i].x+df.x<<" "<<sol[i].y+df.y<<"\n";
return 0;
}