Pagini recente » Cod sursa (job #6072) | Cod sursa (job #1278668) | Cod sursa (job #494073) | Cod sursa (job #404671) | Cod sursa (job #1377678)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int kNMax = 120010;
struct element {double x, y;} Punct[kNMax], Stack[kNMax];
int n, nr_elem;
void Citire() {
ifstream in ("infasuratoare.in");
int aux = 1;
in >> n;
for (int i = 1; i <= n; ++i) {
in >> Punct[i].x >> Punct[i].y;
if ((Punct[i].x < Punct[aux].x) || (Punct[i].x == Punct[aux].x && Punct[i].y < Punct[aux].y))
aux = i;
}
swap(Punct[1], Punct[aux]);
in.close();
}
bool Cmp(element A, element B) {
return (((A.x - Punct[1].x) * (B.y - Punct[1].y) - (A.y - Punct[1].y) * (B.x - Punct[1].x)) >0);
}
void Solve() {
sort(Punct + 2, Punct + n + 1, Cmp);
Stack[++nr_elem] = Punct[1];
Stack[++nr_elem] = Punct[2];
for (int i = 3; i <= n; ++i) {
while ((nr_elem >= 2) && ((Stack[nr_elem].x - Stack[nr_elem - 1].x) * (Punct[i].y - Stack[nr_elem - 1].y) - (Stack[nr_elem].y - Stack[nr_elem - 1].y) * (Punct[i].x - Stack[nr_elem - 1].x)) < 0)
nr_elem--;
Stack[++nr_elem] = Punct[i];
}
}
void Afisare() {
ofstream out("infasuratoare.out");
out << nr_elem << '\n';
for (int i = 1; i <= nr_elem; ++i)
out << fixed << setprecision(6) << Stack[i].x << ' ' << Stack[i].y << '\n';
out.close();
}
int main() {
Citire();
Solve();
Afisare();
return 0;
}