Pagini recente » Cod sursa (job #796658) | Cod sursa (job #2665249) | Cod sursa (job #212468) | Cod sursa (job #1386738) | Cod sursa (job #2011742)
#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
double cross(const cd& x, const cd& y){
return imag(x * conj(y)); }
vector<cd> half_convex_hull_2d(const vector<cd>& v){
vector<cd> rez;
for(const auto x : v){
while(rez.size() >= 2 && cross(rez.rbegin()[0] - rez.rbegin()[1], x - rez.rbegin()[1]) > 0)
rez.pop_back();
rez.push_back(x); }
return rez; }
vector<cd> convex_hull_2d(vector<cd> v){
sort(begin(v), end(v), [&](const cd& a, const cd& b){
return make_pair(real(a), imag(a)) < make_pair(real(b), imag(b)); });
auto h1 = half_convex_hull_2d(v);
reverse(begin(v), end(v));
auto h2 = half_convex_hull_2d(v);
h1.pop_back();
h2.pop_back();
copy(begin(h2), end(h2), back_inserter(h1));
return h1; }
int main(){
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
f >> n;
vector<cd> v(n);
for(auto& p : v){
double x, y;
f >> x >> y;
p = cd { x, y }; }
auto rez = convex_hull_2d(v);
g << rez.size() << '\n';
g << fixed << setprecision(6);
for(const auto p : rez) g << real(p) << ' ' << imag(p) << '\n';
return 0; }