Cod sursa(job #1188390)

Utilizator xtreme77Patrick Sava xtreme77 Data 19 mai 2014 15:53:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
const int MAX = 130000;
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coada{
    double x,y;
};
coada q[MAX],st[MAX];
double determin(coada a,coada b,coada c){
    return static_cast<double> (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(coada a,coada b){
    return determin(q[1],a,b)>0;
}
int n,nr;
int main(){

    fin>>n;
    fin>>q[1].x>>q[1].y;
    for(int i=2;i<=n;++i){
        fin>>q[i].x>>q[i].y;
        if(q[1].x>q[i].x or(q[1].x==q[i].x and q[1].y>q[i].y))swap(q[1],q[i]);
    }
    sort(q+2,q+n+1,cmp);
    st[++nr]=q[1];
    st[++nr]=q[2];
    for(int i=3;i<=n;++i){
        while(determin(st[nr],st[nr-1],q[i])>0 and nr>=2)--nr;
        st[++nr]=q[i];
    }
    fout<<nr<<'\n';
    for(int i=1;i<=nr;++i)fout<<fixed<<setprecision(12)<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}