Cod sursa(job #1589862)

Utilizator robertstrecheStreche Robert robertstreche Data 4 februarie 2016 15:26:04
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <algorithm>
#include <iomanip>
#include <fstream>

#define NMAX 120005

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,nr=2;

struct punct{
   double x,y;
}p[NMAX],S[NMAX];

inline double unghi(int nr,punct a,punct b){
   return p[nr].x*a.y+p[nr].y*b.x+a.x*b.y-a.y*b.x-p[nr].x*b.y-p[nr].y*a.x;
}
inline bool comp(punct a,punct b){
   return unghi(1,a,b)>0;
}
int main()
{
   f>>n;
   for (int i=1;i<=n;i++){
      f>>p[i].x>>p[i].y;
      if (p[i].x<p[1].x || (p[i].x==p[1].x && p[i].y<p[1].y))swap(p[1],p[i]);
   }

   sort(p+2,p+n+1,comp);

   S[1]=p[1];S[2]=p[2];

   for (int i=3;i<=n;i++){
    while (nr>2 && unghi(nr-1,S[nr],p[i])<=0)nr--;
    S[++nr]=p[i];
   }
   g<<nr<<fixed<<setprecision(6)<<'\n';
   for (int i=1;i<=nr;i++)g<<S[i].x<<" "<<S[i].y<<'\n';

   f.close();
   g.close();
}