Pagini recente » Cod sursa (job #488238) | Cod sursa (job #151218) | Cod sursa (job #1385145) | Cod sursa (job #2425282) | Cod sursa (job #800040)
Cod sursa(job #800040)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define LMAX 120010
struct coord {
double x,y;
};
int N;
coord puncte[LMAX];
int stack[LMAX], V;
bool viz[LMAX];
bool cmp(coord A, coord B) {
if (A.x == B.x) {
if (A.y < B.y) return true;
return false;
}
if (A.x < B.x) return true;
return false;
}
int semn(coord A, coord B, coord C) {
return A.x*(B.y-C.y) + A.y*(C.x-B.x) + B.x*C.y - B.y*C.x;
}
void convex() {
int step=1;
stack[0]=0, stack[1]=1, V=1;
viz[1]=true;
for (int i=2; !viz[0];) {
while (viz[i]) {
if (i==N-1) step=-1;
i+=step;
}
while (V>0 && semn(puncte[stack[V-1]], puncte[stack[V]], puncte[i])>0)
viz[stack[V--]]=0;
stack[++V]=i;
viz[i]=true;
}
}
int main () {
double x,y;
freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
scanf("%d", &N);
for (int i=0; i<N; ++i) {
scanf("%lf %lf", &puncte[i].x, &puncte[i].y);
}
sort(puncte, puncte+N, cmp);
convex();
printf("%d\n", V);
for(int i=V; i>=0; --i) {
printf("%.6lf %.6lf\n", puncte[stack[i]].x, puncte[stack[i]].y);
}
return 0;
}