Pagini recente » Cod sursa (job #2296286) | Cod sursa (job #2478035) | Cod sursa (job #402861) | Cod sursa (job #2333834) | Cod sursa (job #2128971)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct{double x;double y;}p[120005];
punct S[120005];
double determinant(punct a,punct b,punct c)
{
return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - a.y*b.x;
}
bool verifica(punct i,punct j)
{
double d;
d=determinant(p[1],i,j);
if(d>0)return true;
else return false;
}
int i,j,n,k;
int main()
{
fin>>n;
fin>>p[1].x>>p[1].y;
j=1;
for(i=2;i<=n;++i)
{
fin>>p[i].x>>p[i].y;
if(p[i].x<p[j].x || (p[i].x==p[j].x && p[i].y<p[j].y))j=i;
}
swap(p[1],p[j]);
sort(p+2,p+n+1,verifica);
S[1]=p[1]; S[2]=p[2]; k=2;
for(i=3;i<=n;++i)
{
while(k>1 && determinant(S[k-1],S[k],p[i])<0)--k;
S[++k]=p[i];
}
fout<<k<<'\n';
fout<<fixed;
for(i=2;i<=k;++i)
fout<<setprecision(6)<<S[i].x<<' '<<setprecision(6)<<S[i].y<<'\n';
fout<<setprecision(6)<<S[1].x<<' '<<setprecision(6)<<S[1].y<<'\n';
fin.close(); fout.close();
return 0;
}