Cod sursa(job #3215408)

Utilizator vvvvvvvvvvvvvVusc David vvvvvvvvvvvvv Data 14 martie 2024 21:39:09
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

struct punct{
    double x, y;
};

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120001;
int n, ind = 1;
double minY = INT_MAX;
vector<punct> puncte;
punct hull[NMAX];

inline bool isCounterClockwise(double x1, double y1, double x2, double y2, double x3, double y3){
    return (long double)(y3 - y2) * (x2 - x1) - (x3 - x2) * (y2 - y1) > 0;
}

int main(){
    fin >> n;
    for(int i = 0; i < n; i++){
        double x, y;
        fin >> x >> y;
        if(y < minY){
            minY = y;
            hull[0] = {x, y};
        }
        puncte.push_back({x, y});
    }

    sort(puncte.begin(), puncte.end(), [](punct a, punct b){
        return atan2(a.y - hull[0].y, a.x - hull[0].x) < atan2(b.y - hull[0].y, b.x - hull[0].x);
    });

    hull[ind++] = puncte[1];

    for(int i = 2; i < puncte.size(); i++){
        double x = puncte[i].x, y = puncte[i].y;
        if(!isCounterClockwise(hull[ind - 2].x, hull[ind - 2].y, hull[ind - 1].x, hull[ind - 1].y, x, y)) hull[ind - 1] = {x, y};
        else hull[ind++] = {x, y};
    }

    fout << ind << '\n';
    fout << fixed;
    for(int i = 0; i < ind; i++) fout << setprecision(6) << hull[i].x << ' ' << hull[i].y << '\n';
    return 0;
}