Mai intai trebuie sa te autentifici.
Cod sursa(job #2247754)
Utilizator | Data | 29 septembrie 2018 00:18:41 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.78 kb |
#include <bits/stdc++.h>
using namespace std;
vector < pair <long double , long double > > puncte;
vector < pair <long double , long double >> stivaPuncte;
long double determinant(pair <long double, long double> penultimul, pair <long double, long double> ultimul, pair < long double, long double> actual){
long double rezultat;
rezultat = penultimul.first * ultimul.second + ultimul.first * actual.second + actual.first * penultimul.second -
ultimul.second * actual.first - actual.second * penultimul.first - penultimul.second * ultimul.first;
return rezultat;
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pair <long double, long double> minim = make_pair(1e9 + 1, 1e9 + 1);
f >> n;
for (int i = 1; i <=n; i ++){
long double x, y;
f >> x >> y;
puncte.emplace_back(x,y);
minim = min (minim, make_pair(x, y));
}
for (int i = 0; i < (int)puncte.size(); ++ i)
if (puncte [i] == minim)
{
swap (puncte [i], puncte [0]);
break;
}
sort(puncte.begin() + 1, puncte.end(), [&](auto &a, auto &b) {
return determinant(puncte[0], a, b) < 0;
});
stivaPuncte.push_back(puncte[0]);
stivaPuncte.push_back(puncte[1]);
for (int i = 2; i < (int)puncte.size(); ++ i){
auto x = puncte[i];
while (stivaPuncte.size() > 1 and determinant(stivaPuncte[(int)stivaPuncte.size() - 2], stivaPuncte.back(), x) > 0){
stivaPuncte.pop_back();
}
stivaPuncte.push_back(x);
}
reverse(stivaPuncte.begin(), stivaPuncte.end());
g << stivaPuncte.size() << '\n';
for (auto x : stivaPuncte){
g << fixed << setprecision(7) << x.first << ' ' << x.second << "\n" ;
}
return 0;
}