Cod sursa(job #2280024)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 10 noiembrie 2018 11:04:15
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Punct
{
 double x,y,r,t,xprev,yprev;
};

Punct A1,B1,P1;

int pozpunctdreapta(Punct A,Punct B,Punct P);
double crossproduct(Punct A,Punct B,Punct P);

int n,i,dx,dy;
Punct stiva[120005];
int capstiva;
Punct Pmarg,X;
Punct Mem[120005];
bool ok;

int main()
{
 fin>>n;
 Pmarg.x=999999;
 Pmarg.y=999999;
 for (i=1;i<=n;i++)
 {
  fin>>X.x>>X.y;
  X.xprev=X.x;
  X.yprev=X.y;
  Mem[i]=X;
  if (X.x<Pmarg.x)
   Pmarg=X;
  else if (X.x==Pmarg.x&&X.y<Pmarg.y)
   Pmarg=X;
 }
 for (i=1;i<=n;i++)
 {
  dx=Mem[i].x-Pmarg.x;
  dy=Mem[i].y-Pmarg.y;
  Mem[i].r=dx*dx+dy*dy;
  if (dx!=0)
   Mem[i].t=dy/dx;
  else
   Mem[i].t=99999999;
  Mem[i].x=dx;
  Mem[i].y=dy;
 }
 ok=1;
 while (ok==1)
 {
  ok=0;
  for (i=1;i<n;i++)
  {
   if (Mem[i].t>Mem[i+1].t)
   {
    ok=1;
    swap(Mem[i],Mem[i+1]);
   }
   else if ((Mem[i].t==Mem[i+1].t)&&(Mem[i].r>Mem[i+1].r))
   {
    ok=1;
    swap(Mem[i],Mem[i+1]);
   }
  }
 }
 capstiva=2;
 stiva[1]=Mem[1];
 stiva[2]=Mem[2];
 for (i=3;i<=n;i++)
 {
  while (crossproduct(stiva[capstiva-1],stiva[capstiva],Mem[i])<=0&&capstiva>=3)
   capstiva--;
  capstiva++;
  stiva[capstiva]=Mem[i];
 }
 fout<<capstiva<<"\n";
 for (i=1;i<=capstiva;i++)
  fout<<fixed<<setprecision(6)<<stiva[i].xprev<<" "<<stiva[i].yprev<<"\n";
 return 0;
}

int pozpunctdreapta(Punct A,Punct B,Punct P)
{
 if (A.x==B.x)
  return P.x-A.x;
 else if (A.y==B.y)
  return P.x-A.y;
 else
  return (P.x-A.x)*(B.y-A.y)-(P.y-A.y)*(B.x-A.x);
} // Nota x,yA sunt x,y minime iar x,y B sunt x,y maxime.

double crossproduct(Punct A,Punct B,Punct P)
{
 return (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y);
}