Cod sursa(job #2950509)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 3 decembrie 2022 22:27:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>
#define MAXN 120000

struct Point{
    double x;
    double y;
};
bool cmpXy(Point A, Point B){return (A.x < B.x || (A.x == B.x && A.y < B.y));}

float convex(Point a, Point b, Point c){
    float S = (a.x * b.y + b.x * c.y + c.x * a.y) -
              (a.x * c.y + b.x * a.y + c.x * b.y);
    return S;
}
std::vector<Point> upper_hull(const std::vector<Point>& v) {
    int last = 1;
    std::vector<Point> S {v[0], v[1]};
    for(int i = 2; i < (int) v.size(); i++){
        while(last > 0 && convex(S[last - 1], S[last], v[i]) > 0)
            last--, S.pop_back();
        last++, S.push_back(v[i]);
    }
    return S;
}

std::vector<Point> lower_hull(const std::vector<Point>& v) {
    int last = 1;
    std::vector<Point> S {v[0], v[1]};
    for(int i = 2; i < (int) v.size(); i++){
        while(last > 0 && convex(S[last - 1], S[last], v[i]) < 0)
            last--, S.pop_back();
        last++, S.push_back(v[i]);
    }
    return S;
}

int main(){
    FILE*fi,*fo;
    fi = fopen("infasuratoare.in","r");
    fo = fopen("infasuratoare.out","w");
    
    int n;
    fscanf(fi,"%d", &n);
    std::vector<Point> v;
    for(int i = 1; i <= n; i++) {
        double x, y;
        fscanf(fi,"%lf%lf", &x, &y);
        v.push_back({x, y});
    }
    std::sort(v.begin(), v.end(), cmpXy);

    auto upper = upper_hull(v);
    auto lower = lower_hull(v);
    
    fprintf(fo, "%lu\n", lower.size() + upper.size() - 2);
    for(int i = 0; i < (int) lower.size(); i++) {
        const auto& [x, y] = lower[i];
        fprintf(fo,"%f %f\n", x, y);
    }
    for(int i = (int) upper.size() - 2; i > 0; i--) {
        const auto& [x, y] = upper[i];
        fprintf(fo,"%f %f\n", x, y);
    }

    return 0;
}