Cod sursa(job #2777613)

Utilizator ioana0211Ioana Popa ioana0211 Data 23 septembrie 2021 19:25:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct{
    double x, y;
    int ind;
};
punct p[120005], pst;
int pst_ind;
vector<punct> st;
double determinant (punct a, punct b, punct c)
{
    return a.x*(b.y-c.y) + a.y*(c.x-b.x) + b.x*c.y - c.x*b.y;
}
bool cmp(punct a, punct b)
{
    if(determinant(a, pst, b)<0) return 1;
    return 0;
}
int main()
{
    int n;
    fin>>n;
    pst.x=1000000000; pst.y=1000000000;
    for(int i=0; i<n; i++)
    {
        fin>>p[i].x>>p[i].y;
        p[i].ind=i;
        if((p[i].x<pst.x) || (p[i].x==pst.x && p[i].y<pst.y)) pst=p[i], pst_ind=i;
    }
    swap(p[0], p[pst_ind]);
    sort(p+1, p+n, cmp);
    st.push_back(pst);
    st.push_back(p[1]);
    int indst=1;
    for(int i=2; i<n; i++)
    {
        if(determinant(st[indst-1], st[indst], p[i])<0)
            st[indst]=p[i];
        else {
            st.push_back(p[i]); indst++;
        }
    }
    for(int i=0; i<=indst; i++){
        fout<<fixed<<setprecision(12)<<st[i].x;
        fout<<" ";
        fout<<fixed<<setprecision(12)<<st[i].y;
        fout<<"\n";
    }
    return 0;
}