Cod sursa(job #1042045)

Utilizator CatalinaRaduCatalina Elena Radu CatalinaRadu Data 26 noiembrie 2013 15:23:52
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>

using namespace std;

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

typedef pair <double,double> punct;

#define x first
#define y second

const int MAXN=120005;
int n;
punct v[MAXN];
punct stack[MAXN];
int head;

void citire()
{
    f>>n;
    for (int i=1;i<=n;i++)
         f>>v[i].x>>v[i].y;
}

inline double produs_vect (const punct &A, const punct &B, const punct &C)
{
    return (B.x-A.x) * (C.y-A.y) - (B.y-A.y) * (C.x-A.x);

}
inline int cmp (const punct &p1, const punct &p2)
{
    return produs_vect(v[1],p1,p2)<0;
}
void sortare ()
{
    int pos=1;
    for (int i=2;i<=n;i++)
        if (v[i]<v[pos])
        pos=i;
    swap(v[i],v[pos]);
    sort(v+2,v+n+1,cmp);
}
void infasuratoare()
{
    sortare();
    stack[1]=v[1];
    stack[2]=v[2];
    head=2;
    for (int i=3;i<=n;i++)
    {
        while(head>=2 && produs_vect(stack[head-1],stack[head],v[i])>0)
            --head;
        stack[++head]=v[i];
    }
}
void afisare()
{
    g<<fixed;
    g<<head<<"\n";
    for (int i=head;i>=1;--i)
        g<<setprecision(9)<<stack[i].x<<" "<<stack[i].y<<"\n";
}
int main()
{
    citire();
    infasuratoare();
    afisare();
    return 0;
}