Cod sursa(job #1328027)

Utilizator PlatenitesVoicu Cristian Platenites Data 27 ianuarie 2015 21:01:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,k,viz[1200001],s[120001];
float q;
struct puncte
{
    float x,y;
}v[120001];
int sortare (puncte A, puncte B)
{
    if(A.x!=B.x)
        return A.x>B.x;
    return A.y<B.y;
}
double determinant(puncte A,puncte B,puncte C)
{
   //return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
   return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;

}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,sortare);
    for(int i=1;i<=2;i++)
    {
        s[i]=i;
    }
    k=2;viz[1]=0;viz[2]=1;
    for(int i=3;i<=n;i++)
    {
        if(determinant(v[s[k]],v[s[k-1]],v[i])<0)
        {
            viz[i]=1;
            s[++k]=i;
        }
        else
        {
            while(determinant(v[s[k]],v[s[k-1]],v[i])>=0 && k>1)
            {
                viz[s[k]]=0; s[k]=0; k--;
            }
            s[++k]=i;viz[i]=1;
        }
    }
    for(int i=n-1;i>=1;i--)
    {
        if(viz[i]==0)
        {
            if(determinant(v[s[k]],v[s[k-1]],v[i])<0)
            {
                s[++k]=i;viz[i]=1;
            }
            else
            {

                while(determinant(v[s[k]],v[s[k-1]],v[i])>=0 && k>1)
                {
                    viz[s[k]]=0; s[k]=0; k--;
                }
                s[++k]=i;viz[i]=1;
            }
        }
    }
    k--;
    g<<k<<'\n';
    for(int i=k;i>=1;i--)
    {
        g<<setprecision(6)<<fixed<<v[s[i]].x<<" ";
        g<<setprecision(6)<<fixed<<v[s[i]].y<<'\n';
    }
    return 0;
}