Cod sursa(job #3214512)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 14 martie 2024 10:21:36
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,poz,k,i,j;
const int INF=9e7;
#define PAIR pair <double,double>
PAIR V[120012],st[120012];
double det(const PAIR &a,const PAIR &b,const PAIR &c)
{
    return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}
bool cmp(const PAIR &a,const PAIR &b)
{
    double d=det({0,0},a,b);
    if(d!=0)
        return d>0;
    else
        return a.first*a.first+a.second*a.second>b.first*b.first+b.second*b.second;

}
int main()
{
    fin>>n;
    poz=0;
    V[0]={INF,INF};
    for(i=1;i<=n;i++)
    {
        fin>>V[i].first>>V[i].second;
        if(V[i].second<V[poz].second||(V[i].second==V[poz].second&&V[i].first<V[poz].first))
            poz=i;
    }
    V[0]=V[poz];
    V[poz]=V[1];
    V[1]=V[0];
    for(i=1;i<=n;i++)
    {
        V[i].first-=V[0].first;
        V[i].second-=V[0].second;
    }
    sort(V+2,V+n+1,cmp);
    /**
    Pentru puncte coliniare
    for(j=3;j<=n;j++)
        if(det(V[1],V[2],V[j]))
            break;
    i=2;
    j--;
    while(i<j)
    {
        swap(V[i],V[j]);
        i++;
        j--;
    }**/
    st[1]=V[1];
    st[2]=V[2];
    k=2;
    for(i=3;i<=n;i++)
    {
        while(k>=2&&det(st[k-1],st[k],V[i])<0)
            k--;

        st[++k]=V[i];
    }
    fout<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<setprecision(9)<<fixed<<st[i].first+V[0].first<<" "<<st[i].second+V[0].second<<"\n";
    return 0;
}