Cod sursa(job #690068)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 25 februarie 2012 10:13:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120002
using namespace std;

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

struct pct{long double x,y;}V[nmax];
int P[nmax],St[nmax];
int N,start;


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

inline long double semn(int a,int b,int c)//determinantul caracteristic triunghiului
{
    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()
{
    int i,k=0;
    in>>N;
    start = 1;
    for(i=1;i<=N;i++)
    {
        in>>V[i].x>>V[i].y;
        if((V[i].x<V[start].x)||(V[i].x==V[start].x&&V[i].y<V[start].y))
            start = i;
    }
    for(i=1;i<=N;i++)
        if(i!=start)P[++k]=i;
    sort(P+1,P+N,cmp());
    //pun in stiva nodul de start
    St[++St[0]] = start;
    for(i=1;i<N;i++)
    {
        while(St[0]>=2&&semn(St[St[0]-1],St[St[0]],P[i])>0)St[0]--;//cat timp am cel putin 2 puncte si determinantul este pozitiv
        St[++St[0]] = P[i];
    }
    out<<fixed<<setprecision(6);
    out<<St[0]<<'\n';
    for(i=St[0];i;i--)out<<V[St[i]].x<<' '<<V[St[i]].y<<'\n';
    return 0;
}