Cod sursa(job #3196175)

Utilizator TheAndreiEnache Andrei Alexandru TheAndrei Data 22 ianuarie 2024 23:26:14
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define nMax 150005

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point {double x, y;};

point points[nMax];
vector <point> ans;

int startingPoint (int n){
    int idx = 0;

    for (int i=1; i<n; ++i){
        if (points[i].x < points[idx].x || (points[i].x == points[idx].x && points[i].y < points[idx].y))
            idx = i;
    }

    return idx;
}

double orientation (point a, point b, point c){
    return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

bool cmp (point a, point b){
    return orientation(points[0], a, b) < 0; // ordine trigonometrica
}

void findAns (int n){
    ans.push_back (points[0]);
    ans.push_back (points[1]);

    for (int i=2; i<n; ++i){
        while (ans.size() >= 2 && orientation(ans[ans.size() - 2], ans.back(), points[i]) >= 0)
            ans.pop_back();

        ans.push_back(points[i]);
    }
}

int main(){
    int n;

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

    swap(points[0], points[startingPoint(n)]);
    sort(points + 1, points + n, cmp);

    findAns(n);

    fout<<ans.size()<<"\n";
    for (point p:ans){
        fout<<p.x<<" "<<p.y<<"\n";
    }
    return 0;
}