Cod sursa(job #1537558)

Utilizator arvlgeArdeleanu Vlad George arvlge Data 27 noiembrie 2015 15:40:34
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,top,pos,s[120010];
typedef pair <double,double> punct;
punct t[120010];

double determinant(punct a, punct b, punct c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(punct a,punct b){
    return (determinant(t[1],a,b)<0);
}

int main(){
    in>>n;

    pos=1;

    for(int i=1 ; i<=n ; i++){
        in>>t[i].x>>t[i].y;
        if(t[i]<t[pos])
            pos=i;
    }

    swap(t[1],t[pos]);

    sort(t+2,t+n11,cmp);

    s[++top]=1;

    for( int i=2 ; i<=n ; i++ ){
        while(top>1 && determinant(t[s[top-1]],t[s[top]],t[1])>0)
            top--;
        s[++top]=i;
    }

    out<<top+1<<"\n";

    while(top){

        out<<fixed<<setprecision(6)<<t[s[top]].x<<" "<<t[s[top]].y<<"\n";

        top--;
    }

    out.close();

    return 0;
}