Cod sursa(job #2376103)

Utilizator Alex221Dumitru Alexandru Alex221 Data 8 martie 2019 13:39:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define MAXN 121000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{ double x;
  double y;
}v[MAXN];
double det(punct a, punct b, punct c)
{ double d=(a.x*b.y)+(b.x*c.y)+(c.x*a.y)-(c.x*b.y)-(b.x*a.y)-(a.x*c.y);
    return d;
}
bool cmp(punct a, punct b)
{ double D=det(v[1],a,b);
  return D>0;
}
int a[MAXN],n,k;
int main()
{ f>>n;
  for(int i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
  for(int i=2;i<=n;i++)
    if(v[1].x>v[i].x || (v[1].x==v[i].x && v[1].y>v[i].y)) swap(v[1],v[i]);
  sort(v+2,v+n+1,cmp);
  a[++k]=1;
  a[++k]=2;
  for(int i=3;i<=n;i++)
  { while(k>=2 && det(v[a[k-1]],v[a[k]],v[i])<0) k--;
     a[++k]=i;
  }
  g<<k<<'\n';
  for(int i=1;i<=k;i++)
    g<<setprecision(12)<<fixed<<v[a[i]].x<<" "<<v[a[i]].y<<'\n';
    return 0;
}