Pagini recente » Cod sursa (job #1430614) | Cod sursa (job #1322045) | Cod sursa (job #1079380) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 128 | Cod sursa (job #2880770)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
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 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 = 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 < hullSize; i++)
// cout << hull[i].x << " " << hull[i].y << '\n';
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;
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--;
// cout << pts[i].x << " " << pts[i].y << " - (scoate) " << side[sp + 1].x << " " << side[sp + 1].y << '\n';
}
hull[++sp] = pts[i];
}
// cout << '\n';
// cout << side[sp - 1].x << " " << side[sp-1].y << '\n';
//cout << '\n';
return sp + 1 - ind;
}