Pagini recente » Borderou de evaluare (job #3365399) | Cod sursa (job #3366945) | Cod sursa (job #3365504) | Cod sursa (job #3366830) | Cod sursa (job #3365399)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 12e4;
int n, vf;
pair <double, double> v[NMAX + 5], stiva[NMAX + 5];
double produs_vect (pair<double, double> a, pair<double, double> b, pair<double, double> c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
bool cmp (pair<double, double> A, pair<double, double> B) {
return produs_vect(v[1], A, B) < 0;
}
int main () {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].first >> v[i].second;
int min_panta = 1;
for (int i = 2; i <= n; i++) {
if (v[i] < v[min_panta])
min_panta = i;
}
swap(v[1], v[min_panta]);
sort (v + 2, v + 1 + n, cmp);
stiva[++vf] = v[1];
stiva[++vf] = v[2];
for (int i = 3; i <= n; i++) {
while (vf >= 2 && produs_vect(stiva[vf - 1], stiva[vf], v[i]) > 0)
vf--;
stiva[++vf] = v[i];
}
fout << fixed << setprecision(6);
fout << vf << "\n";
for (int i = vf; i >= 1; i--) // invers acelor ceasornicului
fout << stiva[i].first << " " << stiva[i].second << "\n";
return 0;
}