Cod sursa(job #1606070)

Utilizator Darius15Darius Pop Darius15 Data 19 februarie 2016 20:03:35
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,varf,p,st[120001],ind[120001],l;
float x[120001],y[120001];
bool cmp(int a,int b)
{
  return (y[a]-y[p])*(x[b]-x[p])<(y[b]-y[p])*(x[a]-x[p]);
}
bool det(int a,int b,int c)
{
  return (x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-x[c]*y[b]-x[a]*y[c]-x[b]*y[a])<0;
}
int main()
{
    f>>n;
    x[0]=1<<31-1,y[0]=1<<31-1;
    for (i=1;i<=n;i++){
      f>>x[i]>>y[i];
      if (x[i]<x[p] || x[i]==x[p] && y[i]<y[p])
        p=i;
    }
    for (i=1;i<=n;i++)
      if (i!=p)
      ind[++l]=i;
    sort(ind+1,ind+n,cmp);
    st[varf=1]=p;
    for (i=1;i<=l;i++)
    {
      while(varf>=2 && det(st[varf-1],st[varf],ind[i]))
        varf--;
      st[++varf]=ind[i];
    }
    g<<varf<<'\n';
    g<<fixed<<setprecision(12);
    for (i=1;i<=varf;i++)
    g<<x[st[i]]<<' '<<y[st[i]]<<'\n';
    return 0;
}