Pagini recente » Cod sursa (job #978262) | Cod sursa (job #2163821) | Cod sursa (job #3230821) | Cod sursa (job #711712) | Cod sursa (job #1040788)
#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>
#include <iomanip>
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 = 1; i <= N; i++)
{
fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
}
qsort(v, N, sizeof(point), compare);
st[1] = 1; st[2] = 2; u = 2;
vis[2] = true;
for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p)))
{
if (vis[i])
continue;
while (u >= 2 && cross_product(v[st[u-1]], v[st[u]], v[i]) < EPS)
vis[st[head--]] = false;
st[++head] = i;
vis[i] = true;
}
fprintf (g, "%d\n", u-1);
for (int i = 0 ; i < u; i++)
fprintf (g, "%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
fclose(f); fclose(g);
return 0;
}