Pagini recente » Cod sursa (job #2855099) | Cod sursa (job #2129618) | Cod sursa (job #186705) | Cod sursa (job #1196512) | Cod sursa (job #1165288)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAX = 120120;
const double EPS = 1e-12;
#define PII pair<double, double>
#define x first
#define y second
int N, head;
int stk[MAX];
bool inStack[MAX];
PII P[MAX];
void citire() {
ifstream in("infasuratoare.in");
in >> N;
for(int i = 1; i <= N; i++) {
in >> P[i].x >> P[i].y;
} in.close();
}
double crossProduct(PII O, PII A, PII B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
void solve() {
sort(P + 1, P + N + 1);
stk[1] = 1;
stk[2] = 2;
inStack[2] = true;
head = 2;
for(int i = 1, p = 1; i; i += (p = (i == N ? -p : p))) {
if(inStack[i]) continue;
while(head >= 2 && crossProduct(P[ stk[head - 1] ], P[ stk[head] ], P[i]) < EPS) {
inStack[ stk[head--] ] = false;
}
stk[++head] = i;
inStack[i] = true;
}
}
void afisare() {
ofstream out("infasuratoare.out");
out << head - 1 << "\n";
for(int i = 1; i < head; i++) {
out << fixed << setprecision(6) << P[ stk[i] ].x << " " << P[ stk[i] ].y << "\n";
} out.close();
}
int main() {
citire();
solve();
afisare();
}