Pagini recente » Cod sursa (job #2173094) | Cod sursa (job #36039) | Cod sursa (job #2919175) | Cod sursa (job #2858609) | Cod sursa (job #1989206)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int Nmax = 120001;
struct punct
{
double x, y;
};
int N, nrp;
punct P[Nmax], St[Nmax];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double det(const punct &A, const punct &B, const punct &C)
{
return (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x) ;
}
bool compd(const punct &A, const punct &B)
{
return det(P[1], A, B) < 0;
}
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;
int pmin = 1; //pozitia celui mai mic x
for(int i = 1; i <= N; i++)
{
f >> P[i].x >> P[i].y;
if(compx(P[i], P[pmin]))
pmin = i;
}
swap(P[1], P[pmin]);
}
void afisare()
{
g << nrp << '\n';
g << fixed << setprecision(6);
for(int i = nrp; i >= 1; i--)
g << St[i].x << ' ' << St[i].y << '\n';
}
void Graham()
{
sort(P + 2, P + N + 1, compd);
St[1] = P[1];
St[2] = P[2];
nrp = 2;
for(int i = 3; i <= N; i++)
{
while(nrp >= 2 && det(St[nrp - 1], St[nrp], P[i]) > 0)
nrp--;
St[++nrp] = P[i];
}
}
int main()
{
citire();
Graham();
afisare();
return 0;
}