Pagini recente » Cod sursa (job #615694) | Cod sursa (job #1846594) | Cod sursa (job #1937825) | Cod sursa (job #139117) | Cod sursa (job #3252834)
#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) {}
};
#define define_point_operator(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_operator(+)
define_point_operator(-)
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<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;
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]);
}
fout<<q.size()<<'\n';
for(auto &i:q)
fout<<i.x<<' '<<i.y<<'\n';
return 0;
}