Pagini recente » Cod sursa (job #1108328) | Cod sursa (job #2080229)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
const int NMAX = 120000;
int n, top;
pair <double, double> puncte[NMAX + 1];
int stiva[NMAX + 1];
bool in_stiva[NMAX + 1];
void citeste() {
f >> n;
for (int i = 1; i <= n; i++) {
f >> puncte[i].first >> puncte[i].second;
}
}
bool semn(pair <double, double> p1, pair <double, double> p2, pair <double, double> p3) {
double det = 0;
det += p1.first * p2.second;
det += p2.first * p3.second;
det += p3.first * p1.second;
det -= p2.second * p3.first;
det -= p3.second * p1.first;
det -= p1.second * p2.first;
return det < 0;
}
void rezolva() {
sort(puncte + 1, puncte + n + 1);
top = 2;
stiva[1] = 1;
stiva[2] = 2;
in_stiva[2] = true;
int pas = 1;
for (int i = 3; i >= 1; i += pas) {
if (i == n) pas = -1;
if (in_stiva[i]) continue;
while (top >= 2 && semn(puncte[stiva[top - 1]], puncte[stiva[top]], puncte[i])) {
in_stiva[stiva[top]] = false;
top--;
}
stiva[++top] = i;
in_stiva[i] = true;
}
}
void scrie() {
g << top - 1 << '\n';
for (int i = 1; i < top; i++) {
g << fixed << setprecision(6) << puncte[stiva[i]].first << ' ' << puncte[stiva[i]].second << '\n';
}
}
int main() {
citeste();
rezolva();
scrie();
}