Pagini recente » Cod sursa (job #1833415) | Cod sursa (job #1101117) | Cod sursa (job #1164504) | Diferente pentru problema/pwca intre reviziile 5 si 4 | Cod sursa (job #1067305)
#include <cstdio>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define Nmax 120005
int N;
pair<double, double> M[Nmax];
pair<double, double> S[Nmax];
int vf;
void read()
{
scanf("%d",&N);
for (int i = 1; i <= N; ++i)
scanf("%lf %lf",&M[i].x,&M[i].y);
}
inline double cross_product(const pair<double,double> A, const pair<double,double> B, const pair<double,double> C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
class cmp{
public:
bool operator()(const pair<double,double> p1, const pair<double,double> p2) const
{
return cross_product(M[1], p1, p2) < 0;
}
};
void sortare()
{
int pz = 1;
for (int i = 2; i <= N; ++i)
if (M[i] < M[pz])
pz = i;
swap(M[1], M[pz]);
sort(M + 2, M + N + 1, cmp());
}
void convex_hull()
{
sortare();
S[1] = M[1];S[2] = M[2];vf = 2;
for (int i = 3; i <= N; ++i)
{
while (vf >= 2 && cross_product(S[vf - 1], S[vf], M[i]) > 0)
--vf;
S[++vf] = M[i];
}
}
void afish()
{
printf("%d\n",vf);
for (int i = vf; i >= 1; --i)
printf("%.6lf %.6lf\n",S[i].x,S[i].y );
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
convex_hull();
afish();
}