Pagini recente » Cod sursa (job #1374304) | Cod sursa (job #154800) | Cod sursa (job #2168112) | Cod sursa (job #1553817) | Cod sursa (job #1341413)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct rct
{
double first,second;
}pc[120002],aux;
int n,m,stiva[120002],varf,minim;
double semn(rct x,rct y,rct z)
{
return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}
bool compara(rct x,rct y)
{
return semn(pc[1],x,y)>0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>pc[i].first>>pc[i].second;
if(pc[i].second < pc[minim].second)
minim=i;
else
if(pc[i].second==pc[minim].second && pc[i].first<pc[minim].first)
minim=i;
}
aux=pc[1];
pc[1]=pc[minim];
pc[minim]=aux;
sort(pc+2,pc+n+1,compara);
for(int i=1;i<=n;i++)
{
while(varf>=2 && semn(pc[i],pc[stiva[varf]],pc[stiva[varf-1]]) > 0 )
varf--;
stiva[++varf]=i;
}
cout<<varf<<'\n';
for(int i=1;i<=varf;i++)
cout<<fixed<<setprecision(12)<<pc[stiva[i]].first<<" "<<pc[stiva[i]].second<<'\n';
return 0;
}