Pagini recente » Cod sursa (job #1935944) | Cod sursa (job #2714944) | Cod sursa (job #372876) | Cod sursa (job #2037438) | Cod sursa (job #1040082)
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include<cstdlib>
using namespace std;
#define NMAX 120001
#define EPS 1e-12
struct point
{
double x, y;
};
int st[NMAX];
bool viz[NMAX];
int compare(const void *a, const void *b)
{
point* _a = (point*)a ;
point* _b = (point*)b;
if ( _a->x == _b->x )
return _a->y - _b->y;
else
return _a->x - _b->x;
}
double convex (point A, point B, point C)
{
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
int main()
{
int N;
FILE *f = fopen ("infasuratoare.in", "r");
FILE *g = fopen ("infasuratoare.out", "w");
fscanf (f, "%d", &N);
point v[NMAX];
//v = new point[N];
for (int i = 0; i < N; i++)
{
fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
}
qsort(v, N, sizeof(point), compare);
st[0] = 0; st[1] = 1; int u = 1, p = 0, j = 0;
viz[1] = 1; int l = 0;
while ( j >= 0 )
{
if (j == N-1)
{
p *= -1;
}
j += p;
if ( viz[j] ) continue;
while (u >= 1 && convex(v[st[u-1]], v[st[u]], v[j]) < EPS)
viz[st[u--]] = 0;
st[++u] = j;
viz[j] = 1;
if (j == 0 && l == 0)
{
p++;
l = 1;
}
}
fprintf (g, "%d\n", u-1);
for (int i = 0 ; i < u-1; i++)
fprintf (g, "%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
fclose(f); fclose(g);
return 0;
}