Pagini recente » Cod sursa (job #1913847) | Cod sursa (job #2966741) | Cod sursa (job #1113430) | Cod sursa (job #2488160) | Cod sursa (job #2374844)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 120005;
const int INF = 1000000000;
const double eps = 1.e-12;
struct Punct {
double x,y ;
};
int st[NMAX];
Punct v[NMAX];
Punct ll;
double d(Punct p1, Punct p2, Punct p3) {
return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x);
}
int u(Punct p1, Punct p2, Punct p3) {
double det = d(p1, p2, p3);
if(fabs(det) < eps) {
return 0;
}
else {
if(det >= eps) {
return 1;
}
else {
return -1;
}
}
}
bool cmp(Punct first, Punct second) {
int cp = u(ll, first, second);
if(cp == 1) {
return 1;
}
else {
return 0;
}
}
int main() {
int n;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
ll.x = ll.y = INF;
for(int i = 0; i < n; i++) {
scanf("%lf%lf", &v[i].x, &v[i].y);
bool ok = 0;
if(ll.y - v[i].y >= eps) {
ok = 1;
}
else if(fabs(ll.y - v[i].y) < eps){
if(ll.x - v[i].x >= eps) {
ok = 1;
}
}
if(ok == 1) {
swap(ll, v[i]);
}
}
v[0] = v[n] = ll;
sort(v + 1, v + n, cmp);
st[0] = 0;
st[1] = 1;
int top = 1;
for(int i = 2; i <= n; i++) {
while(top >= 1 && u(v[st[top - 1]], v[st[top]], v[i]) <= 0) {
top--;
}
st[++top] = i;
}
printf("%d\n", top);
for(int i = 0; i < top; i++) {
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
}
return 0;
}