Cod sursa(job #3208949)

Utilizator nicholas9onicaOnica Nicholas Andrei nicholas9onica Data 1 martie 2024 16:37:03
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Punct
{
    double x,y;
};
Punct punctul_vietii;
int distanta(Punct a)
{
    return (a.x-0)*(a.x-0)+(a.y-0)*(a.y-0);
}
int cadran(Punct a)
{
    if(a.x>0 && a.y>=0)
        return 1;
    else if(a.x<=0 && a.y>0)
        return 2;
    else if(a.x<0 && a.y<=0)
        return 3;
    else if(a.x>=0 && a.y<0)
        return 4;
}
long long cross_product(Punct &a, Punct &b)
{
    return punctul_vietii.x*a.y+a.x*b.y+punctul_vietii.y*b.x-a.y*b.x-b.y*punctul_vietii.x-a.x*punctul_vietii.y;
}
long long det(Punct a, Punct b, Punct c)
{
    return c.x*a.y+a.x*b.y+c.y*b.x-a.y*b.x-b.y*c.x-a.x*c.y;
}
bool cmp(Punct a,Punct b)
{
   if(cadran(a)==cadran(b))
  {
        if(cross_product(a,b)==0)
            return distanta(a)<distanta(b);
        return cross_product(a,b)>0;
    }
//return cadran(a)<cadran(b);
}
Punct v[120008];
vector<Punct>st;
double minst=1e9,minj=1e9;
int main()
{
    long long i,j,n,poz;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].x<minst)
        {
            minst=v[i].x;
            punctul_vietii=v[i];
            poz=i;
        }
        else if(v[i].x==minst && v[i].y<minj)
        {
            minj=v[i].y;
            punctul_vietii=v[i];
            poz=i;

        }
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    st.push_back(v[1]);
    st.push_back(v[2]);
    for(i=3;i<=n;i++)
    {
        while(st.size()>1 && det(st[st.size()-2],st[st.size()-1],v[i])<0)
        {
            st.pop_back();
        }
        st.push_back(v[i]);
    }

   // for(int i=1;i<=n;i++)
    //{
   //     cout<<v[i].x<<" "<<v[i].y<<"\n";
   // }
    fout<<st.size()<<"\n";
//    fout<<punctul_vietii.x<<" "<<punctul_vietii.y<<"\n";

    for(i=0;i<st.size();i++)
    {
        fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';
    }
    return 0;
}