Pagini recente » Cod sursa (job #705203) | Cod sursa (job #2238947) | Cod sursa (job #352555) | Borderou de evaluare (job #1321742) | Cod sursa (job #2007191)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n,mipoz,st[120005],vf;
typedef pair <double,double> punct;
punct p[120010];
double determinant(punct A,punct B,punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int comp(punct A,punct B)
{
if(determinant(p[1],A,B)<0) return true;
return false;
}
void read()
{
f>>n;
for(int i=1;i<=n;++i)
{
f>>p[i].x>>p[i].y;
if(p[i]<p[mipoz]) mipoz=i;
}
}
int main()
{
read();
swap(p[1],p[mipoz]);
sort(p+2,p+n+1,comp);
st[++vf]=1;
for(int i=2;i<=n;++i)
{
while(vf>1&&determinant(p[st[vf-1]],p[st[vf]],p[i])>0) --vf;
st[++vf]=i;
}
g<<vf<<'\n';
while(vf)
{
g<<setprecision(6)<<fixed<<p[st[vf]].x<<' '<<p[st[vf]].y<<'\n';
--vf;
}
return 0;
}