Pagini recente » Cod sursa (job #688200) | Cod sursa (job #2504494) | Cod sursa (job #37955) | Cod sursa (job #1431074) | Cod sursa (job #1488621)
#include <bits/stdc++.h>
using namespace std;
const int kPoints = 1 << 17;
const double eps = 1e-12;
int n, from;
int stk[kPoints];
bool use[kPoints];
pair <double, double> v[kPoints];
void Read() {
ifstream fin ("infasuratoare.in");
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].first >> v[i].second;
}
double crossProd (const pair <double, double>& From, const pair <double, double> &a, const pair <double, double> &b) {
return (a.first - From.first) * (b.second - From.second) - (b.first - From.first) * (a.second - From.second);
}
void Solve() {
bool path = false;
sort(v + 1, v + n + 1);
from = 2;
stk[1] = 1, stk[2] = 2;
use[2] = true;
for (int i = 1; i > 0 ; path |= i == n, i -= path ? 1 : -1 ) {
if (use[i])
continue;
while (from >= 2 and crossProd(v[stk[from - 1]], v[stk[from]], v[i]) < eps)
use[stk[from]] = false, --from;
use[i] = true;
stk[++from] = i;
}
}
void Print() {
ofstream fout ("infasuratoare.out");
fout << from - 1 << fixed << setprecision(12) << "\n";
for (int i = 1 ; i < from ; ++i)
fout << v[stk[i]].first << " " << v[stk[i]].second << "\n";
}
int main() {
Read();
Solve();
Print();
}