Pagini recente » Cod sursa (job #1222809) | Cod sursa (job #2198182) | Cod sursa (job #35118) | Cod sursa (job #2521600) | Cod sursa (job #2880794)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int NMAX = 12e4;
const double INF = 1e15, EPS = 1e-13;
struct point {
double x, y;
};
point pts[NMAX], hull[NMAX + 1];
double dabs(double a);
bool eq(double a, double b);
double slope(point a, point b);
bool cmp(point a, point b);
int buildSide(int n, point side[], int ind);
int buildHull(int n);
int main()
{
int n, hullSize;
FILE *fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(fin, "%lf%lf", &pts[i].x, &pts[i].y);
fclose(fin);
sort(pts, pts + n, cmp);
hullSize = buildHull(n);
FILE *fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", hullSize);
for (int i = 0; i < hullSize; i++)
fprintf(fout, "%.9lf %.9lf\n", hull[i].x, hull[i].y);
fclose(fout);
return 0;
}
double dabs(double a) {
if (a < 0)
a = -a;
return a;
}
bool eq(double a, double b) {
return (dabs(a - b) < EPS);
}
double slope(point a, point b) {
if (eq(a.x, b.x))
if (b.y > a.y)
return INF;
else return -INF;
return (b.y - a.y) / (b.x - a.x);
}
bool cmp(point a, point b) {
if (eq(a.x, b.x))
return a.y > b.y;
return a.x < b.x;
}
int buildSide(int n, point side[], int ind) {
int sp = ind;
side[ind] = pts[0];
for (int i = 1; i < n; i++) {
while (sp > ind && slope(side[sp - 1], side[sp]) < slope(side[sp], pts[i]))
sp--;
hull[++sp] = pts[i];
}
return sp + 1 - ind;
}
int buildHull(int n) {
int hullSize = 0;
hullSize += buildSide(n, hull, 0);
for (int i = 0; i < (hullSize >> 1); i++)
swap(hull[i], hull[hullSize - i - 1]);
for (int i = 0; i < n; i++)
pts[i].y = -pts[i].y;
for (int i = 0; i < hullSize; i++)
hull[i].y = -hull[i].y;
hullSize--;
hullSize += buildSide(n, hull, hullSize);
hullSize--;
for (int i = 0; i < hullSize; i++)
hull[i].y = -hull[i].y;
return hullSize;
}