Cod sursa(job #1920472)

Utilizator TrascaAndreiTrasca Andrei TrascaAndrei Data 10 martie 2017 01:03:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX = 120005;

struct punct{
    double x,y;
}p[MAX];

int n,vf;
int stiva[MAX];

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

inline bool cmp(punct a,punct b){
    return det(a,b,p[1])>0;
}

void problema_Initial(){
    fin>>n;
    int i,poz=1;
    for(i=1;i<=n;i++){
        fin>>p[i].x>>p[i].y;
        if(p[poz].x>p[i].x || (p[poz].x==p[i].x && p[poz].y>p[i].y))
            poz=i;
    }
    swap(p[1],p[poz]);
    sort(p+2,p+n+1,cmp);
}

void convex_Hull(){
    stiva[++vf]=1;
    stiva[++vf]=2;
    for(int i=3;i<=n;i++){
        while(vf>=2 && det(p[stiva[vf-1]],p[stiva[vf]],p[i])<0)
            vf--;
        stiva[++vf]=i;
    }
}

int main()
{
    problema_Initial();
    convex_Hull();
    fout<<vf<<'\n';
    for(int i=vf;i>0;i--)
        fout<<setprecision(6)<<fixed<<p[stiva[i]].x<<" "<<p[stiva[i]].y<<'\n';
    return 0;
}