Cod sursa(job #2476106)

Utilizator Oana024Oana Mocanu Oana024 Data 18 octombrie 2019 09:19:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct pct{double x,y;}v[120001];
long long  n,i,poz=1,s[120001],vf;

double  arie(pct a,pct b,pct c)
{
 return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}

long long dist(pct a,pct b)
{
 return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

bool mycmp(pct a,pct b)
{
 if(arie(v[1],a,b)>0)return 1;
 if(arie(v[1],a,b)==0)return dist(v[1],a)<dist(v[1],b);
 if(arie(v[1],a,b)<0)return 0;
}

int main()
{
 f>>n;
 for(i=1;i<=n;i++)f>>v[i].x>>v[i].y;
 poz=1;
 for(i=2;i<=n;i++)if(v[i].y<v[poz].y||(v[i].y==v[poz].y&&v[i].x<v[poz].x))poz=i;
 swap(v[poz],v[1]);
 sort(v+2,v+n+1,mycmp);
 cout<<endl;
 s[1]=1;s[2]=2;vf=2;int nr=0;
 for(i=3;i<=n;i++){
                   if(arie(v[s[vf-1]],v[s[vf]],v[i])>0)s[++vf]=i;
                   else if(arie(v[s[vf-1]],v[s[vf]],v[i])==0)s[vf]=i;
                   else{
                        while(vf>2&&arie(v[s[vf-1]],v[s[vf]],v[i])<0)vf--;
                        s[++vf]=i;
                       }

                  }
 for(i=1;i<=vf;i++)v[i]=v[s[i]];
 n=vf;
 g<<n<<'\n';
 for(i=1;i<=n;i++)g<<fixed<<setprecision(12)<<v[i].x<<" "<<v[i].y<<'\n';


    return 0;
}