Cod sursa(job #3250374)

Utilizator vladsoartavlad sofronea vladsoarta Data 20 octombrie 2024 14:55:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.59 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#define mkp make_pair
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct punct
{
    long double x,y;
    long double uOX;
} p[120001];
int n,i;
vector<pair<punct,bool>>conv;

punct pjosmax= {1e9,1e9,0};
int indpfirst;

long double lvec(punct p1,punct p2)
{
    int dif1 = p1.x-p2.x;
    int dif2 = p1.y-p2.y;
    return sqrt(dif1*dif1 + dif2*dif2);
}

long double calcunghi(punct p1,punct p2)
{
    long double lungp1= lvec(p1,{0,0,0}),lungp2=1,lungfin = lvec(p1,p2);
    return (lungfin*lungfin - lungp1*lungp1 - lungp2*lungp2) / (-2*lungp1*lungp2);
}

bool cmp(punct a,punct b)
{
    if(a.uOX != b.uOX)
        return a.uOX < b.uOX;
    return a.x < b.x;
}

long double arie(punct p1,punct p2,punct p3)
{
    return (long double)(p1.x*p2.y + p1.y*p3.x + p2.x*p3.y - p1.x*p3.y - p1.y*p2.x - p2.y*p3.x)/2;
}

int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>p[i].x>>p[i].y;
        if(p[i].y < pjosmax.y)
        {
            pjosmax = p[i];
            indpfirst = i;
        }
        else if(p[i].y == pjosmax.y&&pjosmax.x>p[i].x)
        {
            pjosmax = p[i];
            indpfirst = i;
        }
    }
    for(i=1; i<=n; i++)
    {
        if(i == indpfirst)
            continue;
        punct newpct = {p[i].x-pjosmax.x,p[i].y-pjosmax.y,0};
        long double cosu = calcunghi(newpct,{1,0,0});

        p[i].uOX = acos(cosu);
    }

    sort(p+1,p+n+1,cmp);

    conv.push_back(mkp(pjosmax,1));
    n++;
    p[n] = pjosmax;
    for(i=2; i<=n; i++)
    {
        if(conv[conv.size()-1].second)
        {
            if(conv[conv.size()-1].first.y<p[i].y)
                conv.push_back(mkp(p[i],1));
            else
            {
                conv.push_back(mkp(p[i],0));
            }
        }
        else
        {
            if(conv[conv.size()-1].first.y>p[i].y)
                conv.push_back(mkp(p[i],0));
            else
            {
                while(conv[conv.size()-1].first.y<=p[i].y&&conv[conv.size()-1].second!=1)
                    conv.pop_back();
                if(conv[conv.size()-1].first.y<p[i].y)
                    conv.push_back(mkp(p[i],1));
                else
                    conv.push_back(mkp(p[i],0));
            }
        }
    }

    cout<<conv.size()-1<<'\n';
    for(int h=0; h<conv.size()-1; h++)
    {
        cout<<fixed<<setprecision(6)<<conv[h].first.x<<" "<<conv[h].first.y<<'\n';
    }
    return 0;
}