Cod sursa(job #1499845)

Utilizator zertixMaradin Octavian zertix Data 11 octombrie 2015 11:10:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>
#define pub push_back
#define pob pop_back
using namespace std;

double x,y;
int n;
struct punct
{
    double x,y;
} D[125000];

vector <punct> sus,jos;

bool cmp(punct A,punct B)
{
    if (A.x==B.x)
        return A.y<B.y;
    return A.x<B.x;
}

void citire()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);

    for (int i=1; i<=n; ++i)
    {

        scanf("%lf%lf",&D[i].x,&D[i].y);
    }

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

double det(punct A,punct B,punct C)
{
    return ((B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y));
}

int main()
{
    citire();
    int i;
    sus.pub(D[1]);
    sus.pub(D[2]);
    jos.pub(D[1]);
    jos.pub(D[2]);

    for (int i=3; i<=n; ++i)
    {
        int sm=sus.size();

        while (sm>=2 && det(sus[sm-2],sus[sm-1],D[i])>0) ///creez infasuratoarea de sus, sterg pana cand gasesc
                                                        ///un punct care face graficul sa rastoarne apa
        {
            sus.pob();
            --sm;
        }
        sus.pub(D[i]);


        int jm=jos.size();

        while (jm>=2 && det(jos[jm-2],jos[jm-1],D[i])<0) ///creez graficul astfel incat sa tina apa
        {
            jos.pob();
            --jm;
        }
        jos.pub(D[i]);

    }

    if (sus[0].x==jos[0].x && jos[0].y==sus[0].y)
        jos.erase(jos.begin());

    if (sus[sus.size()-1].x==jos[jos.size()-1].x && jos[jos.size()-1].y==sus[sus.size()-1].y)
        jos.pob();

    printf("%d\n",sus.size()+jos.size());



    for(i=0; i<jos.size(); i++)
        printf("%lf %lf\n",jos[i].x,jos[i].y);

    for(i=sus.size()-1; i>=0; i--)
        printf("%lf %lf\n",sus[i].x,sus[i].y);


    return 0;
}