Cod sursa(job #2277873)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 6 noiembrie 2018 22:51:34
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <float,float> a[120001],s[120001];

int n;
int main()
{
    fin>>n;
    for(int i=1;  i<=n;  i++)
    fin>>a[i].first>>a[i].second;

    sort(a+1,a+n+1);
 int top=0;
    s[++top]=a[1];
    s[++top]=a[2];
//cout<<s[top].first<<" "<<s[top].second;
   for(int i=3;i<=n;i++)
     {
         s[++top]=a[i];
            while(top>=3&&s[top-2].first*s[top-1].second+s[top-1].first*s[top].second+s[top].first*s[top-2].second-s[top].first*s[top-1].second-s[top-2].first*s[top].second-s[top-1].first*s[top-2].second<0)
                {
                top--;
                s[top]=s[top+1];
                }
     }
int k=top;
s[++top]=a[n-1];
    for(int i=n-2;i>=1;i--)
            {
                s[++top]=a[i];
            while(top>=k+2&&s[top-2].first*s[top-1].second+s[top-1].first*s[top].second+s[top].first*s[top-2].second-s[top].first*s[top-1].second-s[top-2].first*s[top].second-s[top-1].first*s[top-2].second<0)
                {
                    top--;
                    s[top]=s[top+1];
                }
            }
top--;
fout<<top<<"\n";
for(int i=1;i<=top;i++)
  fout<<s[i].first<<" "<<s[i].second<<"\n";

    return 0;
}