Pagini recente » Cod sursa (job #2637979) | Cod sursa (job #1249114) | Cod sursa (job #3202653) | Cod sursa (job #1097112) | Cod sursa (job #3217376)
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef pair<double,double> pct;
int n;
pct v[120001];
double det(pct a, pct b, pct c) {
return a.first*b.second+b.first*c.second+c.first*a.second-
b.second*c.first-a.second*b.first-c.second*a.first;
}
bool comp(pct a, pct b) {
return det(v[1],a,b)>0;
}
int32_t main()
{in>>n;
int mn=1;
for(int i=1;i<=n;++i) {
in>>v[i].first>>v[i].second;
mn=(v[i].first<v[mn].first || v[i].first==v[mn].first && v[i].second<v[mn].second) ? i : mn;
}
swap(v[1],v[mn]);
sort(v+2,v+n+1,comp);
int k=2; v[n+1]=v[1];
for(int i=3;i<=n+1;++i) {
while(k>=2 && det(v[k-1],v[k],v[i])<0)
k--;
v[++k]=v[i];
}
out<<k-1<<'\n';
for(int i=1;i<k;++i)
out<<fixed<<setprecision(6)<<v[i].first<<' '<<v[i].second<<'\n';
return 0;
}