Pagini recente » Cod sursa (job #1241920) | Cod sursa (job #871127) | Cod sursa (job #1762171) | Cod sursa (job #160437) | Cod sursa (job #3292321)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define double long double
#define int long long
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,i;
struct point{
double x,y;
bool operator <(point b)const{
if(x!=b.x)
return x < b.x;
return y < b.y;
}
}v[120001];
double cross_product(const point& A, const point& B, const point& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(point a,point b)//sortare panta
{
return cross_product(v[1],a,b)< 0;
}
int32_t main()
{
cin>>n;
for(i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
}
int pos=1;
for(i=2;i<=n;i++)
if(v[i] < v[pos])
pos = i;
swap(v[pos],v[1]);
sort(v+2,v+1+n,cmp);
vector<int>stk;
stk.push_back(1);
stk.push_back(2);
for(i=3;i<=n;i++){
while(stk.size() > 2 && cross_product(v[stk[stk.size()-2]],v[stk[stk.size()-1]],v[i]) > 0){
stk.pop_back();
}
stk.push_back(i);
}
cout<<stk.size()<<'\n';
for(int h=stk.size()-1;h>=0;h--)
cout<<fixed<<setprecision(9)<<v[stk[h]].x<<" "<<v[stk[h]].y<<'\n';
return 0;
}