Pagini recente » Cod sursa (job #2740325) | Cod sursa (job #1496307) | Cod sursa (job #1996553) | Cod sursa (job #2906922) | Cod sursa (job #2132117)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const double EPS = 1e-12;
const int Nmax = 120001;
struct punct
{
double x, y;
};
int N, H;
punct P[Nmax];
int St[Nmax];
bool viz[Nmax];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double det(const punct &A, const punct &B, const punct &C)
{
return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}
bool compx(const punct &A, const punct &B)
{
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
void citire()
{
f >> N;
for(int i = 1; i <= N; i++)
f >> P[i].x >> P[i].y;
}
void afisare()
{
g << H << '\n';
g << fixed << setprecision(6);
for(int i = 1; i <= H; i++)
g << P[St[i]].x << ' ' << P[St[i]].y << '\n';
}
void inf_convex()
{
sort(P + 1, P + N + 1, compx);
St[1] = 1;
St[2] = 2;
H = 2;
viz[2] = 1;
for(int i = 3, p = 1; i >= 1; i += p)
{
if(viz[i]) continue;
while(H >= 2 && det(P[St[H - 1]], P[St[H]], P[i]) < EPS)
viz[St[H--]] = 0;
St[++H] = i;
viz[i] = 1;
if(i == N)p = -1;
}
H--;
}
int main()
{
citire();
inf_convex();
afisare();
return 0;
}