Pagini recente » Cod sursa (job #1331871) | Cod sursa (job #2950954) | Cod sursa (job #3040037) | Cod sursa (job #2260404) | Cod sursa (job #1256763)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
struct Punct {
double x, y;
};
const int NMAX = 120000 + 1;
int n, begin, end;
int stiva[NMAX];
bool pus[NMAX];
Punct punct[NMAX];
void citeste() {
f >> n;
for (int i = 1; i <= n; i++) f >> punct[i].x >> punct[i].y;
}
inline bool conditie(Punct a, Punct b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
inline bool semn(Punct a, Punct b, Punct c) {
double x = a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
return (x < 0);
}
void rezolva() {
begin = 1; end = 2;
stiva[1] = 1; pus[1] = true;
stiva[2] = 2; pus[2] = true;
int pas = 1;
for (int i = 3; i > 0; i += pas) {
if (i == n) pas *= (-1);
if (!pus[i]) {
while (end >= 2 && semn(punct[stiva[end - 1]], punct[stiva[end]], punct[i])) pus[stiva[end--]] = false;
pus[i] = true;
stiva[++end] = i;
}
}
g << end << '\n';
for (int i = begin; i <= end; i++) g << fixed << setprecision(6) << punct[stiva[i]].x << ' ' << punct[stiva[i]].y << '\n';
}
int main() {
citeste();
sort(punct + 1, punct + n + 1, conditie);
rezolva();
return 0;
}