Cod sursa(job #2668152)

Utilizator Simon2712Simon Slanina Simon2712 Data 4 noiembrie 2020 16:10:42
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define dbl double
struct ura{
        dbl x,y;
        int tip;
};
ura v[120001];
int st[120001];
bool cmp(ura a,ura b)
{
    if(a.y!=b.y)
        return (a.y<b.y);
    else
        return (a.x<b.x);
}
int arie(dbl x1,dbl y1,dbl x2,dbl y2,dbl x3,dbl y3)
{
    return x1*y2+x2*y3+x3*y1-(y1*x2+y2*x3+y3*x1);
}
int main()
{
    int n,i,nr,nrcp;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    v[1].tip=-1;
    v[n].tip=1;
    for(i=2;i<n;i++)
    {
        if(arie(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y)<0)//stanga
            v[i].tip=1;
        else
            v[i].tip=-1;
    }
    nr=1;
    st[nr]=1;
    for(i=2;i<=n;i++)
    {
        if(v[i].tip==1)
        {
            if(nr>1 && arie(v[st[nr-1]].x,v[st[nr-1]].y,v[st[nr]].x,v[st[nr]].y,v[i].x,v[i].y)<0){
                st[nr]=i;
                nr--;
                while(nr>1 && arie(v[st[nr-1]].x,v[st[nr-1]].y,v[st[nr]].x,v[st[nr]].y,v[i].x,v[i].y)<0){
                    st[nr]=i;
                    nr--;
                }
                nr++;
            }
            else
            {
                nr++;
                st[nr]=i;
            }
        }
    }
    nrcp=nr;
    for(i=n-1;i>=1;i--)
    {
        if(v[i].tip==-1)
        {
            if(nr>1 && arie(v[st[nr-1]].x,v[st[nr-1]].y,v[st[nr]].x,v[st[nr]].y,v[i].x,v[i].y)<0){
                st[nr]=i;
                nr--;
                while(nr>1 && arie(v[st[nr-1]].x,v[st[nr-1]].y,v[st[nr]].x,v[st[nr]].y,v[i].x,v[i].y)<0){
                    st[nr]=i;
                    nr--;
                }
                nr++;
            }
            else
            {
                nr++;
                st[nr]=i;
            }
        }
    }
    nr--;///scot 1
    cout<<nr<<'\n';
    //cout<<v[1].x<<" "<<v[1].y<<'\n';
    for(i=nrcp+1;i<=nr;i++)
        cout<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
    for(i=1;i<=nrcp;i++)
        cout<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
   // cout<<v[n].x<<" "<<v[n].y<<'\n';
    return 0;
}