Cod sursa(job #1605187)

Utilizator Darius15Darius Pop Darius15 Data 18 februarie 2016 20:15:36
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{float x,y;};
int n,i,l,varf;
punct a[100001],st,v[100001],sti[100001];
bool cmp(punct a,punct b)
{
  return (a.y-st.y)*(b.x-st.x)-(b.y-st.y)*(a.x-st.x)<0;
}
float det(punct a,punct b,punct c)
{
  return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
     f>>a[i].x>>a[i].y;
    st=a[1];
    for (i=2;i<=n;i++)
      if (a[i].x<st.x) st=a[i];
      else if (a[i].x==st.x)
               if (a[i].y<st.y)
               st=a[i];
    for (i=1;i<=n;i++)
      if (a[i].x!=st.x || a[i].y!=st.y) v[++l]=a[i];
    sort(v+1,v+l+1,cmp);
    sti[varf=1]=st;
    for (i=1;i<=l;i++)
    {
      while(varf>=2 && det(sti[varf-1],sti[varf],v[i])<0)
        varf--;
      sti[++varf]=v[i];
    }
    g<<varf<<'\n';
    for (i=2;i<=varf;i++)
      g<<sti[i].x<<' '<<sti[i].y<<'\n';
     g<<sti[1].x<<' '<<sti[1].y;
    return 0;
}