Pagini recente » Cod sursa (job #2725651) | Cod sursa (job #2688704) | Cod sursa (job #258810) | Cod sursa (job #559252) | Cod sursa (job #413706)
Cod sursa(job #413706)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N_MAX = 120000;
int n;
double x[N_MAX], y[N_MAX];
int v[N_MAX];
int init;
bool ind_comp ( int a, int b ) {
return (x[a] - x[init]) * (y[b] - y[init]) < (y[a] - y[init]) * (x[b] - x[init]);
}
long double semn ( int p1, int p2, int p3 ) {
return (long double)x[p1]*y[p2] + (long double)x[p2]*y[p3] + x[p3]*y[p1] - (long double)y[p1]*x[p2] - (long double)y[p2]*x[p3] - (long double)y[p3]*x[p1];
}
int main() {
freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
scanf("%d",&n);
init = 0;
for (int i = 0; i < n; ++i) {
scanf("%lf %lf",&x[i],&y[i]);
if (x[i] < x[init] || x[i] == x[init] && y[i] < y[init]) init = i;
}
for (int i = 0, j = 0; i < n; ++i)
if (i != init)
v[j++] = i;
sort(v,v+n-1,ind_comp);
vector<int> st;
st.push_back(init);
for (int i = 0; i < n-1; ++i) {
for (; st.size() > 1 && semn(st[st.size()-2], st[st.size()-1], v[i]) > 0; st.pop_back());
st.push_back(v[i]);
}
reverse(st.begin(), st.end());
printf("%d\n",st.size());
for (int i = 0; i < st.size(); ++i) printf("%.6lf %.6lf\n",x[st[i]],y[st[i]]);
return 0;
}