Cod sursa(job #1916369)

Utilizator ciocan_catalinCiocan Catalin - Iulian ciocan_catalin Data 9 martie 2017 09:15:03
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nmax = 120005;
const double eps = 0.0000000000001;
int N,st[nmax],top;
bool viz[nmax];

struct point
{
    double x,y;
    bool operator < (const point &A)const
    {
        if(y == A.y) return x < A.x;
        return y < A.y;
    }
};
point v[nmax];

inline void Read()
{
    int i;
    fin >> N;
    for(i = 1; i <= N; i++)
    {
        fin >> v[i].x >> v[i].y;
    }
}

inline double Prod(point A, point B, point C)
{
    return -C.x*(B.y-A.y)-C.y*(A.x-B.x)-(B.x*A.y-A.x*B.y);
}


inline void ConvexHull()
{
    sort(v+1,v+N+1);
    int i,semn;
    st[++top] = 1;
    st[++top] = 2;
    viz[2] = true;
    for(i = 3, semn  = 1; i; i+=semn)
    {
        if(viz[i]) continue;
        while(top >= 2 && Prod(v[st[top-1]],v[st[top]],v[i]) <= eps)
        {
            viz[st[top--]] = false;
        }
        st[++top] = i;
        viz[i] = true;
        if(i == N) semn = -1;
    }
    top--;
    fout << top << "\n";
    for(i = 1; i <= top ; i++) fout << v[st[i]].x << " " << v[st[i]].y << "\n";
    fout.close();
}


int main()
{
    Read();
    ConvexHull();
    return 0;
}