Cod sursa(job #1887757)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 21 februarie 2017 19:10:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct punct
{
    double x,y;
} vPuncte[120005],stiva[120005];
int n;
void citire()
{
    double st=0x3f3f3f;
    int indice;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lf%lf",&vPuncte[i].x,&vPuncte[i].y);
        if(st>=vPuncte[i].x)
        {
            if(st==vPuncte[i].x)
            {
                if(vPuncte[indice].y>vPuncte[i].y)
                {
                    st=vPuncte[i].x;
                    indice=i;
                }
            }
            else
            {
                st=vPuncte[i].x;
                indice=i;
            }
        }
    }
    swap(vPuncte[indice],vPuncte[1]);
}
double calculDet(punct p1,punct p2,punct p3)
{
    return(p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.y*p3.x-p3.y*p1.x-p1.y*p2.x);
}
bool cmp(punct p1,punct p2)
{
    if(calculDet(vPuncte[1],p1,p2)<0)
        return false;
    return true;
}
void solve()
{
    sort(vPuncte+2,vPuncte+n+1,cmp);
    /*for(int i=1;i<=n;i++)
    {
        printf("%lf %lf\n",vPuncte[i].x,vPuncte[i].y);
    }
    */
    int indice_stiva=2;
    stiva[1]=vPuncte[1];
    stiva[2]=vPuncte[2];
    for(int i=3; i<=n; i++)
    {
        if(indice_stiva>=2)
        {
            if(calculDet(stiva[indice_stiva-1],stiva[indice_stiva],vPuncte[i])>0)
            {
                stiva[++indice_stiva]=vPuncte[i];
                i++;
            }
            else indice_stiva--;
            i--;
        }
        else
            stiva[++indice_stiva]=vPuncte[i];
    }
    printf("%d\n",indice_stiva);
    for(int i=1; i<=indice_stiva; i++)
        printf("%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    solve();
    return 0;
}