Cod sursa(job #2049778)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 27 octombrie 2017 17:20:58
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#define x first
#define y second
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<long double,long double> PD;
PD a[240005],h[240005];
bool F(PD A,PD B,PD C)
      {return (A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.x*C.y-A.y*B.x<0);}
int n,i,j;
int main()
  {fin>>n;
   for(i=1;i<=n;i++)
      fin>>a[i].x>>a[i].y;
   sort(a+1,a+n+1);
   reverse_copy(a+1,a+n,a+n+1);
   for(i=1;i<=2*n-1;i++)
      {while(j>1&&F(h[j-1],h[j],a[i]))
            j--;
       j++;
       h[j]=a[i];
      }
  fout<<j-1<<"\n";
  fout<<setprecision(12)<<fixed;
  for(i=2;i<=j;i++)
     fout<<h[i].x<<" "<<h[i].y<<"\n";
  }