Pagini recente » Cod sursa (job #2488286) | Cod sursa (job #1996843) | Cod sursa (job #2937853) | Cod sursa (job #2617812) | Cod sursa (job #2132307)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef struct Cr
{
double x;
double y;
} CR;
CR A[120010];
int Stv[120010];
int n;
bool F[120010];
bool cmp(CR a,CR b)
{
if (a.x<b.x)
return 1;
else if (a.x>b.x)
return 0;
return a.y<b.y;
}
double rt(CR Or,CR a,CR b)
{
return (a.x - Or.x) * (b.y - Or.y) - (b.x - Or.x) * (a.y - Or.y);
}
int main()
{
fin>>n;
for (int i=1; i<=n; i++)
fin>>A[i].x>>A[i].y;
sort(A+1,A+n+1,cmp);
Stv[1]=1;
Stv[2]=2;
int cap=2;
F[2]=1;
for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
{
if (F[i]==0)
{
while (cap>=2 && rt(A[Stv[cap-1]],A[Stv[cap]],A[i])<(double)(1e-10))
F[Stv[cap--]]=0;
Stv[++cap]=i;
F[i]=1;
}
}
fout << cap - 1 << "\n";
fout << setprecision(6) << fixed;
for (int i = 1; i < cap; ++i)
fout << A[Stv[i]].x << " " << A[Stv[i]].y << "\n";
return 0;
}