Cod sursa(job #1131323)

Utilizator a96tudorAvram Tudor a96tudor Data 28 februarie 2014 19:22:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define DIF 1e-12
#define NMAX 120010
using namespace std;
typedef pair<double,double> Punct;
Punct V[NMAX],St[NMAX];
int N,H;
inline bool cmp1(double x,double y)
{
    if (x+DIF<y) return true;
    if (y+DIF<x) return false;
    return true;
}
inline double Det(Punct A,Punct B,Punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool cmp(Punct A,Punct B)
{
        return (cmp1(Det(V[1],A,B),1));
}
inline void Sort_Points(int N)
{
    Punct Aux;
    int poz=1;
    for (int i=2;i<=N;++i)
        if (V[i]<V[poz]) poz=i;
    swap(V[1],V[poz]);
    sort(V+2,V+N+1,cmp);
}
inline void Write_Data()
{
    printf("%d\n",H);
    printf("%.9lf %.9lf\n",St[1].x,St[1].y);
    for (int i=H;i>=2;--i)
        printf("%.9lf %.9lf\n",St[i].x,St[i].y);
}
inline void Solve(int N)
{
    H=2; St[1]=V[1]; St[2]=V[2];
    for (int i=3;i<=N;++i)
    {
        while ( H>=2 && Det(St[H-1],St[H],V[i])>0) H--;
        St[++H]=V[i];
    }
}
inline void Load_Data(int &N)
{
    double X,Y;
    scanf("%d",&N);
    for (int i=1;i<=N;++i)
        scanf("%lf%lf",&V[i].x,&V[i].y);
}
int main()
{
    freopen("infasuratoare.in","r",stdin); freopen("infasuratoare.out","w",stdout);
    Load_Data(N);
    Sort_Points(N);
    Solve(N);
    Write_Data();
    fclose(stdin); fclose(stdout);
    return 0;
}