Cod sursa(job #1636304)

Utilizator arhivamanArhiva Man arhivaman Data 7 martie 2016 03:19:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define nMax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double, double> Point;
Point v[nMax];
Point stiva[nMax];
int top, n;
inline double cross_product(const Point& A, const Point& B, const Point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const Point& p1, const Point& p2) {
    return cross_product(v[1], p1, p2) < 0;
}
void read()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
}
void sort_points()
{
    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);
}
void convex()
{
    sort_points();
    stiva[++top]=v[1];
    stiva[++top]=v[2];
    for(int i=3;i<=n;i++)
    {
        while(top>=2 && cross_product(stiva[top-1], stiva[top], v[i])>0)
            top--;
        stiva[++top]=v[i];
    }
}
void write()
{
    fout<<fixed;
    fout<<top<<'\n';
    for(int i=top;i>=1;i--)
        fout<<setprecision(9)<<stiva[i].x<<" "<<stiva[i].y<<'\n';
}
int main()
{
    read();
    convex();
    write();
    return 0;
}