Pagini recente » Cod sursa (job #2189850) | Cod sursa (job #3290391) | Cod sursa (job #3040538) | Cod sursa (job #76576) | Cod sursa (job #1954529)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 120000;
struct Punct{
double x, y;
};
Punct v[NMAX + 5];
double cross_product(Punct P1, Punct P2, Punct P3){
return (P2.x - P1.x) * (P3.y - P2.y) -
(P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(Punct P1, Punct P2, Punct P3){
double cp = cross_product(P1, P2, P3);
if (cp < 0)
return -1;
if (cp > 0)
return 1;
return 0;
}
bool cmp(Punct a, Punct b){
return ccw(v[0], a, b) > ccw(v[0], b, a);
}
int st[NMAX + 5];
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, ind = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i){
double x, y;
scanf("%lf%lf", &x, &y);
v[i] = {x, y};
if (v[i].y < v[ind].y || (v[i].y == v[ind].y && v[i].x < v[ind].x))
ind = i;
}
swap(v[0], v[ind]);
sort(v + 1, v + n, cmp);
st[0] = 0;
st[1] = 1;
int top = 1;
v[n] = v[0];
for (int i = 2; i <= n; ++i){
while (top > 1 && ccw(v[st[top]], v[st[top - 1]], v[i]) != ccw(v[st[top]], v[st[top - 1]], v[st[top - 2]]))
top--;
st[++top] = i;
}
printf("%d\n", top);
for (int i = 0; i < top; ++i){
printf("%f %f\n", v[st[i]].x, v[st[i]].y);
}
return 0;
}