Pagini recente » Cod sursa (job #2371121) | Cod sursa (job #1737248) | Cod sursa (job #1254865) | Cod sursa (job #2720218) | Cod sursa (job #1013077)
#include<fstream>
#include<algorithm>
#include <iomanip>
using namespace std;
int N, head;
struct Punct {
double x,y;
} rez[120005], v[120005];
inline double cross(const Punct& A, const Punct& B, const Punct& C)
{
return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
inline int cmp(const Punct& A, const Punct&B)
{
return cross(v[1],A,B)<0;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin>>N;
for(int i=1;i<=N;++i)
{
fin>>v[i].x>>v[i].y;
}
int k=1;
for(int i=2;i<=N;++i)
{
if((v[i].x<v[k].x) || (v[i].x==v[k].y && v[i].y<v[k].y))
{
k=i;
}
}
Punct a = v[1];
v[1] = v[k];
v[k] = a;
sort(v+2,v+N+1,cmp);
rez[1] = v[1];
rez[2] = v[2];
head = 2;
for(int i=3;i<=N;++i)
{
while(head>=2 && cross(rez[head - 1], rez[head], v[i])>0)
--head;
rez[++head] = v[i];
}
fout<<fixed;
fout<<head<<'\n';
for(int i=head;i>=1;--i)
fout<<setprecision(9)<<rez[i].x<<" "<<rez[i].y<<'\n';
return 0;
}