Pagini recente » Cod sursa (job #472536) | Cod sursa (job #2839040) | Cod sursa (job #2794776) | Cod sursa (job #693376) | Cod sursa (job #695743)
Cod sursa(job #695743)
#include <cstdio>
#include <algorithm>
//#define double long double
const double eps = 0.0000001;
const int maxn = 120005;
using namespace std;
inline double fabs(double x) {
if(x < eps) return -x;
return x;
}
struct Punct {
double x, y;
} v[maxn];
int ord[maxn], st[maxn], N;
bool uz[maxn];
inline bool cmp(const Punct &a, const Punct &b) {
if(fabs(a.x - b.x) < eps) {
return a.y < b.y;
}
return a.x < b.x;
}
inline bool semn(int i, int j, int k) {
double x1 = v[i].x, x2 = v[j].x, x3 = v[k].x, y1 = v[i].y, y2 = v[j].y, y3 = v[k].y;
return ( x1 * y2 + x2 * y3 + y1 * x3 - y2 * x3 - y3 * x1 - y1 * x2) < eps;
}
void ConvexHull() {
int i = 3, step = 1, k = 0;
uz[2] = 1; st[++k] = 1; st[++k] = 2;
while(!uz[1]) {
while(uz[i]) {
if(i == N)
step = -1;
i += step;
}
for(; semn(st[k - 1], st[k], i) && k >= 2; ) {
uz[st[k]] = 0; k--;
}
st[++k] = i; uz[i] = 1;
// i += step; printf("%d\n", step);
}
printf("%d\n", k - 1);
for(int i = 1; i < k; i++)
printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d\n", &N);
for( int i = 1; i <= N; ++i ) {
scanf("%lf%lf\n", &v[i].x, &v[i].y);
//printf("%Lf %Lf\n", v[i].x, v[i].y);
}
sort( v + 1, v + N + 1, cmp);
//for( int i = 1; i <= N; ++i ) printf("%lf %lf\n", v[i].x, v[i].y);
ConvexHull();
return 0;
}