Cod sursa(job #1882074)

Utilizator alex.jilavu17alex jilavu alex.jilavu17 Data 16 februarie 2017 22:23:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,poz,vf,s[120001];
double minx=1000000001,miny=1000000001;
struct punct{
    double x,y;}p[120001];
void cit(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>p[i].x>>p[i].y;
        if(p[i].y==miny)
            if(p[i].x<minx){
                minx=p[i].x;
                poz=i;}
        if(p[i].y<miny){
            miny=p[i].y;
            minx=p[i].x;
            poz=i;}}}
double det(punct p0,punct p1,punct p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
int howtosort(const punct &a,const punct &b){
    return det(p[0],a,b)>0;}
void infasuratoare(){
    vf=1;
    s[0]=0;
    s[1]=1;
    for(int i=2;i<=n;i++){
        while(vf>=1 && det(p[s[vf-1]],p[s[vf]],p[i])<0)
            vf=vf-1;
        vf=vf+1;
        s[vf]=i;}
}
int main(){
    cit();
    int i;
    p[0].x=minx;
    p[0].y=miny;
    for(i=poz;i<n;i++)
        p[i]=p[i+1];
    n--;
    sort(p+1,p+n+1,howtosort);
    infasuratoare();
    for(i=0;i<=vf;i++)
        fout<<fixed<<setprecision(6)<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
    return 0;}