Cod sursa(job #2918007)

Utilizator ezluciPirtac Eduard ezluci Data 9 august 2022 10:11:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
#define last(x) (x.back())
#define penlast(x) (x[x.size()-2])
#define INF 1e9+1
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

const int nMAX = 120e3;
typedef long double ld;

int n;
vector<int> stiv;
struct punct {
   ld x, y, pan;
   bool operator<(const punct&B)const
   {
      if (pan < 0 && B.pan >= 0)
         return false;
      if (pan >= 0 && B.pan < 0)
         return true;
      if (pan != B.pan)
         return pan < B.pan;
      if (pan == 0)
         return x < B.x;
      if (pan == INF)
         return y < B.y;
      return y < B.y;
   }
} pct[nMAX + 1];


ld panta(int i, int j)
{
   if (pct[i].x == pct[j].x)
      return INF;
   else
      return (pct[j].y-pct[i].y) / (pct[j].x-pct[i].x);
}


int main()
{
   fin >> n;
   int min = 0;
   pct[0] = {INF, INF};
   for (int i = 1; i <= n; ++i)
   {
      fin >> pct[i].x >> pct[i].y;

      if (pct[i].y < pct[min].y)
         min = i;
      else if (pct[i].y == pct[min].y && pct[i].x < pct[min].x)
         min = i;
   }

   swap(pct[1], pct[min]);
   for (int i = 2; i <= n; ++i)
      pct[i].pan = panta(1, i);

   sort(pct + 2, pct + n+1);

   stiv.push_back(1);
   stiv.push_back(2);
   for (int i = 3; i <= n+1; ++i)
   {
      punct a = pct[penlast(stiv)];
      punct b = pct[last(stiv)];

      while ((pct[(i-1)%n+1].y-a.y) * (b.x-a.x) <= (b.y-a.y) * (pct[(i-1)%n+1].x-a.x))
      {
         stiv.pop_back();
         a = pct[penlast(stiv)];
         b = pct[last(stiv)];
      }
      stiv.push_back(i);
   }
   stiv.pop_back();

   fout << setprecision(20) << stiv.size() << '\n';
   for (int g : stiv)
      fout << pct[g].x << ' ' << pct[g].y << '\n';
}