Pagini recente » Cod sursa (job #3123939) | Cod sursa (job #951083) | Cod sursa (job #1242005) | Cod sursa (job #1012846) | Cod sursa (job #1414005)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N, vf=2, pmin=1;
struct asd{ double x, y; }a[120005], st[120005];
double crossed_prod(asd A, asd B, asd C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
struct cmp
{
bool operator()(const asd &A, const asd &B)const
{
return crossed_prod(a[1], A, B)<0;
}
};
void go()
{
st[1]=a[1]; st[2]=a[2];
for (int i=3; i<=N; ++i)
{
while (vf>=2 && crossed_prod(st[vf-1], st[vf], a[i])>0)
--vf;
st[++vf]=a[i];
}
}
int main()
{
f>>N;
for (int i=1; i<=N; ++i)
{
f>>a[i].x>>a[i].y;
if (a[i].x<a[pmin].x) pmin=i;
else if (a[i].x==a[pmin].x && a[i].y<a[pmin].y)
pmin=i;
}
swap(a[1], a[pmin]);
sort(a+2, a+N+1, cmp());
g<<fixed<<setprecision(6);
go();
g<<vf<<'\n';
for (int i=vf; i; --i)
g<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}