Cod sursa(job #553979)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 14 martie 2011 14:21:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <algorithm>
#define nmax 120002

using namespace std;

ifstream in("infasurare.in");
ofstream out("infasurare.out");

struct p{double x,y;}V[nmax];
int St[nmax],P[nmax],s,N,i,k;

/*class cmp
{
    public: //dx1*dy2<dy1*dx2
    inline bool operator()(const int&a,const int &b){return (double)((V[a].x-V[s].x)*(V[b].y-V[s].y))<(double)((V[b].x-V[s].x)*(V[a].y-V[s].y));}
};*/
inline bool cmp(const int&a,const int &b){return (double)((V[a].x-V[s].x)*(V[b].y-V[s].y))<(double)((V[b].x-V[s].x)*(V[a].y-V[s].y));}

inline long double semn(int a,int b,int c)//determinantul caracteristic triunghiului format de cele 3 puncte
{
    return (long double)(V[a].x*V[b].y+V[b].x*V[c].y+V[a].y*V[c].x-V[c].x*V[b].y-V[c].y*V[a].x-V[b].x*V[a].y);
}

int main()
{
    in>>N;
    for(i=1;i<=N;i++)
    {
        in>>V[i].x>>V[i].y;
        if(V[i].x<V[s].x||(V[i].x==V[s].x&&V[i].y<V[s].y))
            s=i;
        if(!s)s=1;
    }
    k=1;
    for(i=1;i<=N;i++)
        if(i!=s)P[k++]=i;
    sort(P+1,P+N,cmp);
    //pe stiva plasez potentialele puncte ale infasurarii convexe
    St[++St[0]]=s;
    for(i=1;i<N;i++)
    {
        if(P[i]==s)continue;
        while(St[0]>=2&&semn(St[St[0]-1],St[St[0]],P[i])>0)--St[0];
        St[++St[0]]=P[i];
    }
    out<<St[0]<<'\n'<<V[s].x<<' '<<V[s].y<<'\n';
    for(i=St[0];i>1;--i)out<<V[St[i]].x<<' '<<V[St[i]].y<<'\n';
    return 0;
}