Cod sursa(job #2774957)

Utilizator C_DanyConstantin Daniel C_Dany Data 13 septembrie 2021 17:54:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <iostream>
#include <vector>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <fstream>
#define PI 3.14159265
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");


struct point{
double x;
double y;
};

int             NrPoints;
int             Last;
point           pt;
vector<point>   Points;
vector<point>   UpSolution;
vector<point>   DownSolution;

bool isLeft(point A, point B, point C)
{
   if(A.x == B.x)
      return A.x > C.x;
   if(A.y == B.y)
      return A.y < C.y;


   double m = (B.y - A.y)/(B.x - A.x);
   double n = 0 - A.x * m + A.y;

   return C.y > m * C.x + n;
}

double Angle(point p)
{
    double angle =  acos((double)(abs(p.x) / sqrt(p.x*p.x + p.y*p.y)));

    if(p.x < 0 && p.y >= 0)
        angle = 3.141592653589 - angle;
    if(p.x <= 0 && p.y < 0)
        angle = 3.141592653589 + angle;
    if(p.x > 0 && p.y < 0)
        angle = 2*3.141592653589 - angle;
    return angle;
}

int main()
{
  f>> NrPoints;
  for(int it = 1; it <= NrPoints; it++)
        {
            f>> pt.x >> pt.y;
            Points.push_back(pt);
        }

   sort(begin(Points),end(Points),[](point A, point B)->bool
        {
          if( A.x == B.x)
            return A.y < B.y;
          return A.x < B.x;
        });
    UpSolution.resize(NrPoints);
    UpSolution[0] = Points[0];
    UpSolution[1] = Points[1];
    Last = 1;

    for(int it = 2; it < NrPoints ; it++)
    {
         if(UpSolution[Last].x == Points[NrPoints-1].x && UpSolution[Last].y == Points[NrPoints-1].y )
             break;

         while(Last > 0 && isLeft(UpSolution[Last-1],UpSolution[Last],Points[it]))
                   {
                       UpSolution[Last] = Points[it];
                       Last--;
                   }
          Last++;
          UpSolution[Last] = Points[it];
    }
    UpSolution.resize(Last+1);

    DownSolution.resize(NrPoints);
    DownSolution[0] = Points[0];
    DownSolution[1] = Points[1];
    Last = 1;

    for(int it = 2; it < NrPoints ; it++)
    {
         if(DownSolution[Last].x == Points[NrPoints-1].x && DownSolution[Last].y == Points[NrPoints-1].y )
             break;

         while(Last > 0 && isLeft(DownSolution[Last-1],DownSolution[Last],Points[it]) == false)
                   {
                       DownSolution[Last] = Points[it];
                       Last--;
                   }
          Last++;
          DownSolution[Last] = Points[it];
    }
    DownSolution.resize(Last+1);

    UpSolution.insert(end(UpSolution),begin(DownSolution)+1,end(DownSolution)-1);
    sort(begin(UpSolution),end(UpSolution),[](point A, point B)->bool
         {
             if(Angle(A) == Angle(B))
                 return sqrt(A.x*A.x + A.y*A.y) > sqrt(B.x*B.x + B.y*B.y);

             return Angle(A) < Angle(B);
         });
g.precision(6);
g<<UpSolution.size()<<'\n';
    for(auto it : UpSolution)
        g<<fixed<< it.x * 1.000000<<" "<<it.y <<endl;
return 0;
}