Cod sursa(job #1937217)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 23 martie 2017 20:05:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#include <iomanip>
#define NMAX 120001

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

struct Punct{
double x, y;
friend bool operator <(Punct a, Punct b);
};
Punct P, V[NMAX];
stack <Punct> S;
bool operator <(Punct a, Punct b)
    {
     return (a.y - P.y) * ( b.x - P.x) < (a.x - P.x) * (b.y- P.y)||
        (((a.y - P.y) * ( b.x - P.x) == (a.x - P.x) * (b.y- P.y)) && ((a.x-P.x)*(a.x-P.x) < (b.x-P.x)*(b.x-P.x)));
     ;
    }
int n;

vector<Punct> VEC;

void citire();
void afisare();

double arie(Punct a, Punct b, Punct c);

int main()
{
citire();
afisare();
fin.close();
fout.close();
return 0;
}
void afisare()
    {
     int i;
     fout<<S.size()<<'\n';
     while (!S.empty())
         {
          VEC.push_back(S.top());
          S.pop();
         }
     fout<<fixed<<setprecision(12);
     for (i=VEC.size()-2;i>=0;i--)
         fout<<VEC[i].x<<' '<<VEC[i].y<<'\n';
     fout<<VEC[VEC.size()-1].x<<' '<<VEC[VEC.size()-1].y<<'\n';
    }

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

void citire()
    {
     int i;
     fin>>n;
     fin>>V[0].x>>V[0].y;
     P.x=V[0].x;
     P.y=V[0].y;
     for (i=1;i<n;i++)
         {
          fin>>V[i].x>>V[i].y;
          if (V[i].x<P.x || (V[i].x==P.x && V[i].y<P.y))
            {
             P=V[i];
            }
         }
     V[n]=V[0];
     sort (V, V+n);
     S.push(V[0]);
     for (i=1;i<n;i++)
         {
          //analizez varful stivei cu V[i] si V[i+1]
          if (arie(S.top(), V[i], V[i+1])<=0)
             {
              while (!S.empty())
                 {
                  V[i]=S.top();
                  S.pop();
                  if (arie(S.top(), V[i], V[i+1])>0)
                     {
                      break;
                     }
                 }
             }
          S.push(V[i]);
         }
    }