Pagini recente » Cod sursa (job #725963) | Cod sursa (job #3003417) | Cod sursa (job #38537) | Cod sursa (job #281593) | Cod sursa (job #2402499)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-12;
struct P{
double x, y;
double pt;
}v[120005];
int st[120005];
double cp(P a, P b, P c){
return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
int ccw(P a, P b, P c){
double ccp = cp(a, b, c);
if(ccp >= -eps)
return 1;
return 0;
}
int cmp(P a, P b){
return a.pt < b.pt;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, i, mn, k;
scanf("%d", &n);
mn = 0;
for(i = 0;i < n;i++){
scanf("%lf%lf", &v[i].x, &v[i].y);
v[i].pt = atan2(v[i].y, v[i].x);
if(v[i].x < v[mn].x || (v[i].x == v[mn].x && v[i].y < v[mn].y))
mn = i;
}
for(i = 0;i < n;i++){
v[i].pt = atan2(v[i].y - v[mn].y, v[i].x - v[mn].x);
}
v[mn].pt = -1;
sort(v, v + n, cmp);
k = 1;
for(i = 1;i < n;i++){
while(k > 1 && !ccw(v[st[k - 2]], v[st[k - 1]], v[i]))
k--;
st[k++] = i;
}
while(k > 1 && !ccw(v[st[k - 2]], v[st[k - 1]], v[0]))
k--;
printf("%d\n", k);
for(i = 0;i < k;i++){
printf("%f %f\n", v[st[i]].x, v[st[i]].y);
}
return 0;
}