Pagini recente » Cod sursa (job #673563) | Cod sursa (job #3247161) | Cod sursa (job #2541625) | Cod sursa (job #1342031) | Cod sursa (job #3197318)
#include <bits/stdc++.h>
using namespace std;
using Point = complex<double>;
istream& operator>>(istream &in, Point &a){
double x, y;
in >> x >> y;
a = Point(x, y);
return in;
}
ostream& operator<<(ostream &out, Point &a){
out << fixed << setprecision(10) << a.real() << " " << a.imag();
return out;
}
const double eps = 1e-9;
const double pi = acos(-1);
namespace std {
bool operator<(Point a, Point b) {
if(fabs(a.real() - b.real()) < eps)
return a.imag() < b.imag() - eps;
return a.real() < b.real() - eps;
}
}
double squaredDist(Point a, Point b){
return norm(b - a);
}
double dist(Point a, Point b){///distance from a to b
return abs(b - a);
}
double dot(Point a, Point b){
return (conj(a) * b).real();
}
double cross(Point a, Point b){
return (conj(a) * b).imag();
}
double det(Point a, Point b, Point c){///0 if collinear, positive if (a, b, c) in trigonometric order, negative otherwise
return cross(b - a, c - a) / 2.0;
}
bool areCollinear(Point a, Point b, Point c){
return abs(det(a, b, c)) < eps;
}
double angle(Point a, Point b){
return arg(b - a);
}
vector<Point> v;
vector <Point> halfConvex(vector <Point> v, int half)//half = 1 for upper, -1 for lower
{
vector <Point> ans;
for(auto it:v)
{
while(ans.size() >= 2 && half * det(ans.end()[-2], ans.end()[-1], it) > eps)//change to -eps to eliminate collinear points
ans.pop_back();
ans.push_back(it);
}
return ans;
}
vector<Point> convexHull(vector<Point> v){///returns the convex hull in anti-trigonometric order from the leftmost point
if(v.size() == 1)
return v;
sort(v.begin(), v.end());
if(v.size() == 2)
return v;
auto upper = halfConvex(v, 1);
auto lower = halfConvex(v, -1);
auto ans = upper;
for(int i = lower.size() - 2; i > 0; i--)
ans.push_back(lower[i]);
return ans;
}
int main()
{
#ifndef HOME
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
#endif
int n;
cin >> n;
v.resize(n, Point(0, 0));
for(int i = 0; i < n; i++)
cin >> v[i];
v = convexHull(v);
cout << v.size() << '\n';
reverse(next(v.begin()), v.end());
for(auto it:v)
cout << it << '\n';
return 0;
}