Pagini recente » Cod sursa (job #1097463) | Cod sursa (job #603046) | Cod sursa (job #502712) | Cod sursa (job #1817769) | Cod sursa (job #1723628)
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1.e-12;
const int NMAX = 120005;
struct PII {
double x, y;
bool operator<(PII arg) const {
if(abs(x - arg.x) < EPS)
return y < arg.y;
else
return x < arg.x;
}
};
int sccw(PII a, PII b, PII c) {
double s = (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
if(abs(s) < EPS)
return 0;
if(s>=EPS)
return 1;
else
return -1;
}
PII v[NMAX];
vector<int> upper, lower;
int main(void) {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d",&n);
for(int i=0; i<n; ++i)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v, v+n);
for(int i=0; i<n; ++i) {
while(upper.size()>1 && sccw(v[upper[upper.size()-2]], v[upper[upper.size()-1]], v[i])<0)
upper.pop_back();
upper.push_back(i);
}
for(int i=0; i<n; ++i) {
while(lower.size()>1 && sccw(v[lower[lower.size()-2]], v[lower[lower.size()-1]], v[i])>0)
lower.pop_back();
lower.push_back(i);
}
printf("%d\n",upper.size()+lower.size()-2);
for(int i=0; i<upper.size(); ++i)
printf("%.6f %.6f\n",v[upper[i]].x,v[upper[i]].y);
for(int i=lower.size()-2; i>0; --i)
printf("%.6f %.6f\n",v[lower[i]].x,v[lower[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}