Cod sursa(job #2259914)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 13 octombrie 2018 22:44:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,j,k,nsv,x1,x2;
struct punct
{
    int x,y;
    double up;
};
punct v[105],st[105],sv;
int cmp(punct A,punct B)
{
    if(A.up==B.up)
        if(A.y==B.y)
        return A.x<B.x;
    else
        return A.y<B.y;
    return A.up<B.up;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        if(i==1)
        {
            sv.x=v[i].x;
            sv.y=v[i].y;
            sv.up=0;
            nsv=i;
        }
        else
            if(v[i].y<sv.y||(v[i].y==sv.y&&v[i].x<sv.x))
        {  sv.x=v[i].x;
            sv.y=v[i].y;
            sv.up=0;
            nsv=i;
        }

    }
    for(j=1;j<=n;j++)
        if(j!=nsv)
    {
        v[j].up=(v[j].x-sv.x)/sqrt((v[j].x-sv.x)*(v[j].x-sv.x)+(v[j].y-sv.y)*(v[j].y-sv.y));
        v[j].up=acos(v[j].up);
    }
    sort(v+1,v+n+1,cmp);
    st[1].x=v[1].x;
    st[1].y=v[1].y;
    st[2].x=v[2].x;
    st[2].y=v[2].y;
    k=2;
    if(n>=3)
    {
        st[3].x=v[3].x;
        st[3].y=v[3].y;
        j=3;
        k=3;
        while(j<n)
        {if(st[k-2].x*st[k-2].y+st[k-1].x*st[k].y+st[k].x*st[k-2].y-st[k].x*st[k-1].y-st[k-2].x*st[k].y-st[k-1].x*st[k-2].y>=0)
        {j++;
        k++;
        st[k]=v[j];}
        else
        {
            st[k-1]=st[k];
            k--;
        }
        if(st[k-2].x*st[k-2].y+st[k-1].x*st[k].y+st[k].x*st[k-2].y-st[k].x*st[k-1].y-st[k-2].x*st[k].y-st[k-1].x*st[k-2].y<0)
        {
            st[k-1].x=st[k].x;
            st[k-1].y=st[k].y;
            k--;
        }

        }
        x1=st[k].x;
        x2=st[k].y;
        for(i=n;i>=1&&v[i].up==st[k].up;i--)
            if(v[i].x!=x1||v[i].y!=x2)
        {
            k++;
            st[k]=v[i];
        }
    g<<k<<"\n";
    for(j=1;j<=k;j++)
        g<<st[j].x<<" "<<st[j].y<<"\n";

    }
    return 0;
}