Cod sursa(job #1568853)

Utilizator Darius15Darius Pop Darius15 Data 14 ianuarie 2016 19:29:11
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{float x,y;};
punct a[200001],st[200001];
int n,i,v;
bool cmp(punct b,punct c)
{
  return (((c.x-a[0].x)*(b.y-a[0].y))<((b.x-a[0].x)*(c.y-a[0].y)));
}
bool semn(punct a,punct b,punct c)
{
  return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)<0);
}
int main()
{
    a[0].x=a[0].y=1<<31-1;
    f>>n;
    for (i=1;i<=n;i++){
      f>>a[i].x>>a[i].y;
      if (a[0].x>a[i].x)
        a[0].x=a[i].x,a[0].y=a[i].y;
      else if (a[0].x==a[i].x)
           if (a[0].y>a[i].y)
           a[0].y=a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    st[v=1]=a[0];
    for (i=1;i<=n;i++)
      if (!(a[i].x==a[0].x && a[i].y==a[0].y)){
         while(v>=2 && semn(st[v-1],st[v],a[i]))
              v--;
        st[++v]=a[i];
      }
    g<<v<<'\n';
    g<<fixed<<setprecision(6);
    for (i=2;i<=v;i++)
      g<<st[i].x<<' '<<st[i].y<<'\n';
    g<<st[1].x<<' '<<st[1].y<<'\n';
    return 0;
}