Cod sursa(job #3216162)

Utilizator dragosdragonnIosub Dragos Casian dragosdragonn Data 15 martie 2024 17:58:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct{
  double x;
  double y;
}point[120005];
punct poligon[120005];
int lgPoligon;
bool cmp(punct a,punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x>b.x)
        return 0;
    if(a.x==b.x)
    {
        return (a.y<=b.y);
    }
}
int orientare(punct a,punct b,punct c)
{
    double det=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    if(det>0)
        return 1;
    if(det<0)
        return 2;
    if(det==0)
        return 3;
}
void poligonSus()
{
    for(int i=0;i<n;i++)
    {
        while(lgPoligon>=2 && orientare(poligon[lgPoligon-2],poligon[lgPoligon-1],point[i])!=1)
        {
            lgPoligon--;
        }
        poligon[lgPoligon++]=point[i];
    }
}
void poligonJos()
{
    for(int i=n-3;i>=0;i--)
    {
        while(lgPoligon>=2 && orientare(poligon[lgPoligon-2],poligon[lgPoligon-1],point[i])!=1)
        {
            lgPoligon--;
        }
        poligon[lgPoligon++]=point[i];
    }
}
void citire()
{
    fout<<fixed<<setprecision(6);
    fin>>n;
    for(int i=0;i<n;i++)
    {
        fin>>point[i].x;
        fin>>point[i].y;
    }
    sort(point,point+n,cmp);
    poligonSus();
    poligon[lgPoligon++]=point[n-2];
    poligonJos();
    lgPoligon--;
    fout<<lgPoligon<<'\n';
    for(int i=0;i<lgPoligon;i++)
        fout<<poligon[i].x<<" "<<poligon[i].y<<"\n";
}
int main()
{
    citire();
    return 0;
}