Cod sursa(job #2880770)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 30 martie 2022 08:35:31
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.37 kb
#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;
}