Cod sursa(job #1836163)

Utilizator danutbodbodnariuc danut danutbod Data 27 decembrie 2016 21:59:50
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <fstream>
#define M 120003//
#define MAX 1000000001
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
struct punct
{
    double x,y;
}P[M];
double Det(punct a,punct b, punct c){
  return ((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
}
bool cmp(punct a,punct b)
{
    return Det(P[1],a,b)>0;
}
int n,xmini=MAX,ymini=MAX,poz_min,st[M],vf;
int main()
{
    fi>>n;
    for(int i=1;i<=n;i++)
      fi>>P[i].x>>P[i].y;
    for(int i=1;i<=n;i++)
        if(P[i].x<xmini)xmini=P[i].x;
    for(int i=1;i<=n;i++)
        if(P[i].x==xmini)
          if(P[i].y<ymini){ymini=P[i].y;poz_min=i;}
    swap(P[1],P[poz_min]);
    sort(P+2,P+n+1,cmp);
    P[n+1]=P[1];
    st[1]=1;
    st[2]=2;
    vf=2;
    for(int i=3;i<=n;i++)
    {
        while(vf>1&&Det(P[st[vf-1]],P[st[vf]],P[i])<0)
            vf--;
        st[++vf]=i;
    }
    fo<<vf<<'\n';
    for(int i=1;i<=vf;i++)
        fo<<fixed<<setprecision(6)<<P[st[i]].x<<' '<<P[st[i]].y<<'\n';
    return 0;
}