Pagini recente » Cod sursa (job #906530) | Cod sursa (job #2704176) | Cod sursa (job #968807) | Cod sursa (job #567823) | Cod sursa (job #1807369)
#include <cstdio>
#include <algorithm>
#define NMAX 120010
using namespace std;
struct pct {
double x, y;
};
pct points[NMAX], stack[NMAX];
unsigned int vfS, n;
void citire();
void Graham();
inline bool cmp(const pct&, const pct&);
inline double crossProduct(const pct&, const pct&, const pct&);
void afisare();
int main() {
citire();
Graham();
afisare();
return 0;
}
void citire() {
FILE*fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
unsigned int i;
for (i = 1; i <= n; ++i)
fscanf(fin, "%lf %lf", &points[i].x, &points[i].y);
fclose(fin);
return;
}
void Graham() {
unsigned int bottomLeftPoint = 1, i;
for (i = 2; i <= n; ++i)
if (points[i].y<points[bottomLeftPoint].y || (points[i].y == points[bottomLeftPoint].y && points[i].x<points[bottomLeftPoint].x)) {
bottomLeftPoint = i;
}
swap(points[bottomLeftPoint], points[1]);
sort(points + 2, points + n + 1, cmp);
stack[1] = points[1]; stack[2] = points[2]; vfS = 2;
for (i = 3; i <= n; ++i) {
while (vfS>1 && crossProduct(stack[vfS - 1], stack[vfS], points[i]) <= 0)
--vfS;
stack[++vfS] = points[i];
}
return;
}
inline double crossProduct(const pct &a, const pct &b, const pct &c) {
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
inline bool cmp(const pct &a, const pct &b) {
return crossProduct(points[1], a, b)>0;
}
void afisare() {
FILE*fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", vfS);
unsigned int i;
for (i = 1; i <= vfS; ++i)
fprintf(fout, "%f %f\n", stack[i].x, stack[i].y);
fclose(fout);
return;
}