Cod sursa(job #1607005)

Utilizator king25Ionut Vasi king25 Data 20 februarie 2016 19:18:12
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>

#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double,double> Point;
Point V[100005],stack[100005];
int head,n;
void read(){
    f>>n;
    for(int i=1;i<=n;i++){
        f>>V[i].first>>V[i].second;
    }
}
double cross_product(const Point& A,const Point& B,const Point& C){
    return (B.first-A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first);
}
bool comp1(const Point& A,const Point& B){
    return cross_product(V[1],A,B)<0;
}
void sort_points(){
    int pos=1;
    for(int i=2;i<=n;i++){
        if(V[pos]>V[i]){
            pos=i;
        }
    }
    swap(V[1],V[pos]);
    sort(V+2,V+n+1,comp1);
}
void convex(){
    stack[1]=V[1];
    stack[2]=V[2];
    head=2;
    for(int i=3;i<=n;i++){
        while(head>=2 && cross_product(stack[head-1],stack[head],V[i])>0){
            --head;
        }
        stack[++head]=V[i];
    }
}
void solve(){
    convex();g<<fixed<<head<<endl;
    for(int i=head;i>=1;i--){
        g<<setprecision(9)<<stack[i].first<<" "<<stack[i].second<<endl;
    }
}
int main()
{
    read();
    sort_points();
    solve();
    return 0;
}