Cod sursa(job #1296742)

Utilizator tudi98Cozma Tudor tudi98 Data 21 decembrie 2014 14:39:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;

struct P{
    double x,y;
};

P a[120005];
P v[120005];
int n,M;

inline double cross_Product(const P& A,const P& B,const P& C){
    return A.x*(B.y - C.y) + B.x*(C.y - A.y) + C.x*(A.y - B.y);
}

inline int comp(const P& A,const P& B){
    return cross_Product(a[1],A,B) < 0;
}

void point_sort()
{
    int pos = 1;
    for(int i = 2; i <= n; i++){
        if(a[i].x == a[pos].x){
            if(a[i].y < a[pos].y){
                pos = i;
            }
        }
        else if(a[i].x < a[pos].x){
            pos = i;
        }
    }
    swap(a[1],a[pos]);
    sort(a+2,a+n+1,comp);
}

void convex_hull()
{
    point_sort();
    M = 2;
    v[1] = a[1];
    v[2] = a[2];
    for(int i = 3; i <= n; i++){
        while(M  >= 2 && cross_Product(v[M-1],v[M],a[i]) > 0)
            M--;
        v[++M] = a[i];
    }
}

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");

    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;

    convex_hull();

    fout << M << "\n";
    for(int i = M; i >= 1; i--)
        fout << fixed << setprecision(12) << v[i].x << " " << v[i].y << "\n";

}