Pagini recente » Cod sursa (job #2299077) | Cod sursa (job #1847592) | Cod sursa (job #2187583) | Cod sursa (job #2843239) | Cod sursa (job #1888779)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,vf=0,s[120001];
struct punct{double x,y;};
punct p[120001];
int det(punct i,punct j,punct k){
return (j.x-i.x)*(k.y-i.y)-(j.y-i.y)*(k.x-i.x);
}
bool comp(punct a,punct b){
return det(p[0],a,b)<0;}
int main()
{
int Min=2000000000,Min1=2000000000,i,poz;
fin>>n;
for(i=1;i<=n;i++){
fin>>p[i].x>>p[i].y;
if(p[i].x<Min){ Min=p[i].x;Min1=p[i].y;poz=i;}
else
if(p[i].x==Min&&p[i].y<Min1){ Min=p[i].x;Min1=p[i].y;poz=i;}
}
fin.close();
p[0]=p[poz];
swap(p[poz],p[n]);
sort(p+1,p+n+1,comp);
vf=1;
s[0]=0;s[1]=1;
for(i=2;i<=n-1;i++){
while(vf>=1&&det(p[s[vf-1]],p[s[vf]],p[i])>0)
vf--;
vf++;
s[vf]=i;
}
fout<<vf+1<<'\n';
for(i=vf;i>=0;i--)
fout<<fixed<<setprecision(6)<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
return 0;
}