Pagini recente » Cod sursa (job #552019) | Cod sursa (job #39491) | Cod sursa (job #2697983) | Cod sursa (job #1193442) | Cod sursa (job #2777615)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <valarray>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {
long double x, y;
} puncte[120005], stiva[120005];
int n, nstiva, indprimul;
long double determinant(punct a, punct b, punct c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
long double distanta(punct a, punct b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.x - b.y) * (a.y - b.y));
}
bool comp(punct a, punct b) {
if (determinant(puncte[0], a, b) == 0)
return distanta(puncte[0], a) < distanta(puncte[0], b);
return determinant(puncte[0], a, b) > 0;
}
void citire() {
f >> n;
indprimul = 0;
for (int i = 0; i < n; ++i) {
f >> puncte[i].x >> puncte[i].y;
if (puncte[i].x < puncte[indprimul].x ||
puncte[i].x == puncte[indprimul].x && puncte[i].y < puncte[indprimul].y)
indprimul = i;
}
swap(puncte[0], puncte[indprimul]);
}
void infasuratoare() {
stiva[0] = puncte[0];
stiva[1] = puncte[1];
nstiva = 2;
for (int i = 2; i < n; ++i) {
while (determinant(stiva[nstiva - 2], stiva[nstiva - 1], puncte[i]) <= 0)
nstiva--;
stiva[nstiva++] = puncte[i];
}
}
void afisare() {
g << nstiva << '\n';
for (int i = 0; i < nstiva; ++i)
g << fixed << setprecision(6) << stiva[i].x << ' ' << stiva[i].y << '\n';
}
int main() {
citire();
sort(puncte + 1, puncte + n, comp);
infasuratoare();
afisare();
return 0;
}