Pagini recente » Cod sursa (job #933869) | Cod sursa (job #2972656) | Cod sursa (job #1984612) | Cod sursa (job #1692439) | Cod sursa (job #3252846)
#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct Point
{
T x,y;
Point(const T &_x = 0, const T &_y = 0) : x(_x), y(_y) {}
};
template<typename T>
T compare(const Point<T> &a, const Point<T> &b)
{
return (a.x - b.x) + (a.x - b.x == 0? a.y-b.y : 0);
}
#define define_point_comparator(op)\
template<typename T>\
bool operator op (Point<T> a, const Point<T> &b)\
{\
return compare(a,b) op 0;\
}
#define define_point_operation(op)\
template<typename T>\
Point<T> operator op (Point<T> a, const Point<T> &b)\
{\
a.x = a.x op b.x;\
a.y = a.y op b.y;\
return a;\
}
define_point_comparator(<)
define_point_comparator(>)
define_point_comparator(==)
define_point_comparator(!=)
define_point_comparator(<=)
define_point_comparator(>=)
define_point_operation(+)
define_point_operation(-)
template<typename T>
T signed_area(const Point<T> &a, const Point<T> &b, const Point<T> &c)
{
return (a.x*b.y - a.x*c.y + b.x*c.y - b.x*a.y + c.x*a.y - c.x*b.y)/2;
}
template<typename T>
T area(const Point<T> &a, const Point<T> &b, const Point<T> &c)
{
return abs(signed_area(a,b,c));
}
typedef Point<long double> point;
point v[120000];
int main()
{
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
int n; fin>>n;
int maxi = 0;
point miny = 0;
for(int i=0; i<n; ++i)
{
fin>>v[i].x>>v[i].y;
if(v[i].x < v[maxi].x || (v[i].x == v[maxi].x && v[i].y < v[maxi].y))
maxi = i;
}
swap(v[maxi], v[0]);
sort(v+1, v+n, [&v](const point &a, const point &b){
return signed_area(*v,a,b) > 0 ||
signed_area(*v,a,b) == 0 && a.x <= b.x;
});
deque<point> q;
q.push_back(v[0]);
for(int i=1; i<n; ++i)
{
// cout<<"i = "<<i<<"\n";
// for(auto &i:q)
// {
// cout<<i.x<<' '<<i.y<<'\n';
// }
// cout<<"\n\n";
while(q.size() > 1 && signed_area(*(q.end()-2), q.back(), v[i]) <= 0)
q.pop_back();
q.push_back(v[i]);
}
if(signed_area(*(q.end()-2), q.back(), v[0]) == 0) q.pop_back();
miny = *min_element(q.begin(), q.end(), [](const point &a, const point &b){return a.y < b.y || a.y == b.y && a.x < b.x;});
while(q.front() != miny)
{
q.push_back(q.front());
q.pop_front();
}
fout<<q.size()<<'\n';
for(auto &i:q)
fout<<i.x<<' '<<i.y<<'\n';
return 0;
}