Cod sursa(job #2925808)

Utilizator proflaurianPanaete Adrian proflaurian Data 16 octombrie 2022 09:47:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 120010;
typedef pair<double,double> punct;
punct P[N],st[N];
int n,k;
double delta(punct A,punct B,punct C)
{
    double ret=(A.X*B.Y+B.X*C.Y+C.X*A.Y)-(A.Y*B.X+B.Y*C.X+C.Y*A.X);
    return ret;
}
bool crit(punct A,punct B)
{
    double d=delta(P[0],A,B);
    /// daca P[0],A, vede B in stanga atunci A si B sunt asezate corect in sortare
    if(d>0)return true;
    return false;
}
int main()
{
    /// citire
    f>>n;
    for(int i=0;i<n;i++)
    {
        double x,y;
        f>>x>>y;
        P[i]=make_pair(x,y);
    }
    /// alegem punctul situat cel mai la dreapta si daca am mai multe - cel mai jos
    int i=0;
    for(int j=1;j<n;j++)
        if(P[j]<P[i])
            i=j;
    /// il mutam la inceput
    swap(P[0],P[i]);
    /// sortam punctele trigononetric fata de P[0]
    sort(P+1,P+n,crit);
    /// punem in stiva P[0] si P[1]
    st[0]=P[0];st[1]=P[1];
    k=1;
    for(int j=2;j<n;j++)
    {
        /// pentru fiecare punct:
        /// eliminam ultimul punct din stiva cat timp punctul nou se vede in dreapta
        while(k>1&&delta(st[k-1],st[k],P[j])<=0)
            k--;
        /// apoi adaugam punctul nou
        k++;
        st[k]=P[j];
    }
    /// afisare:
    g<<k+1<<'\n';
    for(int i=0;i<=k;i++)
        g<<fixed<<setprecision(10)<<st[i].X<<' '<<st[i].Y<<'\n';
    return 0;
}