Cod sursa(job #1143342)

Utilizator serbanSlincu Serban serban Data 15 martie 2014 15:02:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

int n,last2,last1;
bool A[120010];
double Z,minx,miny;
struct kt{
double x,y,tg;
};
kt v[120010];
int cmp(kt pp, kt qq)
{
    return pp.tg>qq.tg;
}
int main()
{
    int i;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        if(minx>v[i].x)
            minx=v[i].x,miny=v[i].y;
        if(minx==v[i].x)
            if(miny>v[i].y)
                miny=v[i].y;
    }
    for(i=1;i<=n;i++)
    {
        v[i].x-=minx;
        v[i].y-=miny;
        v[i].tg=atan2(v[i].y,v[i].x);
    }
    sort(v+1,v+n+1,cmp);
    last1=1;
    last2=2;
    A[last1]=true;
    A[last2]=true;
    for(i=3;i<=n;i++)
    {
        Z=v[last1].x*v[i].y+v[i].x*v[last2].y+v[last2].x*v[last1].y-
        v[last1].y*v[i].x-v[i].y*v[last2].x-v[last2].y*v[last1].x;
        if(Z>=0)
        {
            A[i]=true;
            last1=last2;
            last2=i;
        }
        else
        {
            while(Z<0)
            {
                A[last2]=false;
                last2=last1;
                last1--;
                while(!A[last1])
                    last1--;
                Z=v[last1].x*v[i].y+v[i].x*v[last2].y+v[last2].x*v[last1].y-
                v[last1].y*v[i].x-v[i].y*v[last2].x-v[last2].y*v[last1].x;
            }
            if(Z>=0)
            {
                last1=last2;
                last2=i;
                A[i]=true;
            }
        }
    }
    int k=0;
    for(i=1;i<=n;i++)
        if(A[i]==true)
            k++;
    cout<<k<<"\n";
    for(i=n;i>=1;i--)
        if(A[i]==true)
            std::cout<<std::setprecision(12)<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}