Cod sursa(job #2809650)

Utilizator marcumihaiMarcu Mihai marcumihai Data 27 noiembrie 2021 12:26:21
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define eps 0.0000000001
using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

int n;
struct pct
{
    double x;
    double y;
};
pct a[150005];
int s[150005];
int fr[150005];
double ok(pct A, pct B, pct C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-B.x*A.y-A.x*C.y-B.y*C.x;

}

int cmp(pct A, pct B)
{
    if(A.y<B.y)
        return 1;
    return 0;
}


int main()
{
    f>>n;
    for(int i=1; i<=n; ++i)
    {
        f>>a[i].x>>a[i].y;

    }
    sort(a+1, a+n+1, cmp);


    s[1]=1;
    s[2]=2;
    fr[1]=1;
    fr[2]=1;
    int cont=2;

    for(int i=3; i<=n ; ++i)
    {
        if(fr[i]==0)
        {


            while(cont>=2 && ok(a[s[cont-1]],  a[s[cont]], a[i])<=eps)
            {
                fr[s[cont]]=0;
                --cont;
            }
            s[++cont]=i;
            fr[i]=1;
        }
    }
    for(int i=n-1; i>0; --i)
    {
        if(fr[i]==0)
        {

            while(cont>=2 && ok(a[s[cont-1]],  a[s[cont]], a[i])<=eps)
            {
                fr[s[cont]]=0;
                --cont;
            }
            s[++cont]=i;
            fr[i]=1;
        }
    }
    double cost=0;
    g<<cont<<"\n";
    for(int i=1;i<=cont;++i)
        g<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";

    return 0;
}