Cod sursa(job #2358719)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 28 februarie 2019 11:40:24
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <bits/stdc++.h>
#define high 99999999

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Punct
{
 double xp,yp;
};

int nrp;
double xc,yc;
double ymin,xmin;
int punctmin;
long long prod2;
Punct Puncte[120005];
Punct Stiva[120005];
int capstiva;
int i;

bool compareare(Punct,Punct);
long long prod(Punct,Punct,Punct);

int main()
{
 fin>>nrp;
 ymin=xmin=high;
 for (i=1;i<=nrp;i++)
 {
  fin>>xc>>yc;
  if (ymin>yc)
  {
   ymin=yc;
   xmin=xc;
   punctmin=i;
  }
  else if (ymin==yc&&xmin>xc)
  {
   xmin=xc;
   punctmin=i;
  }
  Puncte[i].xp=xc;
  Puncte[i].yp=yc;
 }
 swap(Puncte[1],Puncte[punctmin]);
 punctmin=1;
 sort(Puncte+2,Puncte+1+nrp,compareare);
 capstiva++;
 Stiva[capstiva]=Puncte[1];
 for (i=2;i<=nrp;i++)
 {
  prod2=prod(Stiva[capstiva-1],Stiva[capstiva],Puncte[i]);
  if (prod2==0)
  {
   if (capstiva>1)
    Stiva[capstiva]=Puncte[i];
   else
   {
    capstiva++;
    Stiva[capstiva]=Puncte[i];
   }
  }
  else if (prod2>0)
  {
   capstiva++;
   Stiva[capstiva]=Puncte[i];
  }
  else
  {
   while (prod2<0)
   {
    capstiva--;
    prod2=prod(Stiva[capstiva-1],Stiva[capstiva],Puncte[i]);
   }
   capstiva++;
   Stiva[capstiva]=Puncte[i];
  }
 }
 fout<<capstiva<<"\n";
 for (i=1;i<=capstiva;i++)
  fout<<Stiva[i].xp<<" "<<Stiva[i].yp<<"\n";
 return 0;
}

bool compareare(Punct X1,Punct X2)
{
 long long prodcomp;
 double dist1,dist2;
 dist1=(X1.xp-Puncte[1].xp)*(X1.xp-Puncte[1].xp)+(X1.yp-Puncte[1].yp)*(X1.yp-Puncte[1].yp);
 dist2=(X2.xp-Puncte[1].xp)*(X2.xp-Puncte[1].xp)+(X2.yp-Puncte[1].yp)*(X2.yp-Puncte[1].yp);
 prodcomp=prod(Puncte[1],X1,X2);
 if (prodcomp>0)
  return 1;
 else if (prodcomp==0&&dist1<dist2)
  return 1;
 return 0;
}

long long prod(Punct Origin,Punct X1,Punct X2)
{
 return (X1.xp-Origin.xp)*(X2.yp-Origin.yp)-(X2.xp-Origin.xp)*(X1.yp-Origin.yp);
}