Pagini recente » Cod sursa (job #1197987) | Cod sursa (job #1248175) | Cod sursa (job #2208690) | Cod sursa (job #1118024) | Cod sursa (job #3273766)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
const int NMAX = 120000;
struct punct {
double x, y;
};
int N, nrp;
punct P[NMAX+1], S[NMAX+1];
double det (const punct &A, const punct &B, const punct &C) {
return (A.x - B.x) * (B.y - C.y) - (A.y - B.y) * (B.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;
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 Graham() {
sort(P+2, P+N+1, compd);
S[1] = P[1];
S[2] = P[2];
nrp = 2;
for (int i=3; i<=N; i++) {
while(nrp >= 2 && det(S[nrp-1], S[nrp], P[i]) < 0)
nrp--;
S[++nrp] = P[i];
}
}
void afisare() {
g << nrp << '\n';
g << fixed << setprecision(6);
for(int i = 1; i<=nrp; i++)
g << S[i].x << ' ' << S[i].y << '\n';
}
int main()
{
citire();
Graham();
afisare();
f.close();
g.close();
return 0;
}