Pagini recente » Cod sursa (job #1995620) | Cod sursa (job #2434376) | Cod sursa (job #2045047) | Cod sursa (job #2158636) | Cod sursa (job #2285296)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 1000000006
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x, y;
}v[120005], a, s[120005];
int n, vf;
bool cmp(point b, point c)
{
double x=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
if(x==0) return b.y<c.y||(b.y==c.y&&b.x<c.x);
else return x<0;
}
int main()
{
a.x=INF, a.y=INF;
fin>>n;
for(int i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<a.y) a=v[i];
else if(v[i].y==a.y&&v[i].x<a.x) a=v[i];
}
sort(v+1, v+n+1, cmp);
//for(int i=1;i<=n;++i) fout<<v[i].x<<" "<<v[i].y<<"\n";
v[n+1]=v[1], v[n+2]=v[2];
a=v[1];
point b=v[2], c=v[3];
s[++vf]=v[1];
s[++vf]=v[2];
int nr=0;
for(int i=3;i<=n+2;++i)
{
a=s[vf-1], b=s[vf], c=v[i];
while(!cmp(b, c)&&vf>1)
{
vf--;
nr--;
a=s[vf-1];
b=s[vf];
}
s[++vf]=c;
nr++;
}
fout<<nr<<"\n";
fout<<fixed;
fout<<setprecision(12)<<s[1].x<<" "<<setprecision(12)<<s[1].y<<"\n";
for(int i=nr;i>=2;--i) fout<<setprecision(12)<<s[i].x<<" "<<setprecision(12)<<s[i].y<<"\n";
return 0;
}