Cod sursa(job #2983548)

Utilizator BiancaMMIVMariciuc Bianca BiancaMMIV Data 22 februarie 2023 16:42:29
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include<bits/stdc++.h>

using namespace std;

//ifstream f("file.in");
//ifstream f("p2sah.in");
//ofstream g("p2sah.out");

struct Point {
    float x, y;

    int crossZ(Point p) {
        return x*p.y - y*p.x;
    }

    bool notEqual(Point p) {
        return x != p.x || y != p.y;
    }
};

bool verif[120000];

vector<Point> readPoints(char* path) {

    ifstream f(path);
    int n;
    f>>n;
    vector<Point> points(n);

    for(int i=0; i<n; i++) {
        f >> points[i].x >> points[i].y;
    }

    return points;
}

Point minimX(vector<Point>& points) {

    Point minP = points[0];

    for(int i=1; i<points.size(); i++) {
        if(minP.x > points[i].x)
            minP = points[i];
    }

    return minP;
}

bool allCrossIsPositive(Point u, Point p, vector<Point> &points) {

    for(int i=0; i<points.size(); i++) {

        Point v = {points[i].x - p.x, points[i].y - p.y};

        if(points[i].notEqual(p)) {
            if(u.crossZ(v) < 0)
                return false;
        }
    }

    return true;
}


Point nextPointOnPoly(vector<Point> &points, Point p) {

    for(int i=0; i<points.size(); i++) {

        Point u = {points[i].x- p.x, points[i].y - p.y};
        
        if(points[i].notEqual(p) && !verif[i]) {

            if(allCrossIsPositive(u, p, points)) {
                verif[i] = true;
                return points[i];
            }
        }
    }

    cout << "aici nu trebuia sa se ajunga";
    exit(-1);
}

vector<Point> findPolygon(vector<Point>& points) {
    
    vector<Point> poly;
    
    Point minP = minimX(points);
    Point p = minP;

    do {

        p = nextPointOnPoly(points, p);
        poly.push_back(p);

    } while(p.notEqual(minP));

    return poly;
}

int main(){

    vector<Point> points = readPoints("infasuratoare.in");

    vector<Point> result = findPolygon(points);

    ofstream g("infasuratoare.out");
    g<<result.size()<<'\n';
    for(Point p : result) {
        g << fixed << setprecision(6) << p.x<<" "<< p.y <<'\n';
    }   

    return 0;

}