Cod sursa(job #2658775)

Utilizator AlexVolatiluVoicu Alex AlexVolatilu Data 15 octombrie 2020 01:00:42
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.45 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <limits>
#include <vector>

using namespace std;

#define FILE_NAME_PATH_LEN 256

const double eps = 1.e-20;

struct point{
    double x, y;
};

bool comparePoints (const point &a, const point &b) {
    double d1 = (double)b.x - a.x;
    if (fabs(d1) < eps) {
        double d2 = (double)b.y - a.y;
        if (fabs(d2) < eps) {
            return true;
        } else {
            return d2 > 0 ? true : false;
        }
    } else {
        return d1 > 0 ? true : false;
    }
}

FILE *infile, *outfile;

double crossprod(point p1, point p2, point p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

vector<point> quickhull(vector<point> PointList, point APoint, point BPoint)
{
    vector<point> filteredPoints;

    if (PointList.empty()) {
        return filteredPoints;
    }

    point maxDistPoint = PointList.back();
    PointList.pop_back();
    double maxDistance = crossprod(APoint, BPoint, maxDistPoint);
    
    double crtDistance;
    for (point p : PointList) {
        crtDistance = crossprod(APoint, BPoint, p);
        if (crtDistance >= -eps) {
            if (crtDistance - maxDistance > eps) {
                if (maxDistance >= -eps) {
                    filteredPoints.push_back(maxDistPoint);
                }
                maxDistance = crtDistance;
                maxDistPoint = p;
            } else {
                filteredPoints.push_back(p);
            }
        }
    }

    if (maxDistance >= eps) {
        vector<point> First, Last;
        First = quickhull(filteredPoints, APoint, maxDistPoint);
        Last = quickhull(filteredPoints, maxDistPoint, BPoint);
        First.push_back(maxDistPoint);
        First.insert(First.end(), Last.begin(), Last.end());
        return First;
    } else {
        return vector<point>();
    }
}

vector<point> convex_hull(vector<point> PointList)
{
    sort(PointList.begin(), PointList.end(), comparePoints);
    vector<point> Lower, Upper;
    point APoint, BPoint;

    APoint = PointList.front();
    BPoint = PointList.back();

    PointList.erase(PointList.begin());
    PointList.pop_back();

/*
    for (point p : PointList) {
        fprintf(outfile, "%lf %lf\n", (p.x), (p.y));
    }
    fprintf(outfile, "\n");
*/
    Upper = quickhull(PointList, APoint, BPoint);
    Lower = quickhull(PointList, BPoint, APoint);

    vector<point> res;
    res.push_back(APoint);
    res.insert(res.end(), Upper.begin(), Upper.end());
    res.push_back(BPoint);
    res.insert(res.end(), Lower.begin(), Lower.end());

    return res;
}

int main()
{
    char infilepath[FILE_NAME_PATH_LEN] = "infasuratoare.in";//"./input/input_0.txt";
    char outfilepath[FILE_NAME_PATH_LEN] = "infasuratoare.out";//"./output/out_input_0.txt";

    infile = fopen(infilepath, "r");
    outfile = fopen(outfilepath, "w");

    //numeric_limits<double>().epsilon
    printf("epsilon %.30lf\n", eps);

    point auxpoint;
    int inputPointsNum;
    vector<point> inputPointList;

    fscanf(infile, "%d", &inputPointsNum);

    for(int i = 0; i < inputPointsNum; i++) {
        fscanf(infile, "%lf %lf", &(auxpoint.x), &(auxpoint.y));
        inputPointList.push_back(auxpoint);
    }

    vector<point> Hullpoints = convex_hull(inputPointList);
    fprintf(outfile, "%d\n", Hullpoints.size());
    for (point p : Hullpoints) {
        fprintf(outfile, "%lf %lf\n", (p.x), (p.y));
    }
    fprintf(outfile, "\n");

    fclose(infile);
    fclose(outfile);

    return 0;
}