Cod sursa(job #2552630)

Utilizator aeliusdincaaelius dinca aeliusdinca Data 21 februarie 2020 01:24:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct coord
{
    double x,y;
}sts[120001],v[120001],stdr[120001];
bool cmp(coord a, coord b)
{
    if(a.y<b.y)
        return true;
    if(a.y==b.y&&a.x<b.x)
        return true;
    return false;
}
bool crb(coord p1,coord p2,coord p3)
{
    if((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x)<=0)
        return false;
    return true;
}
int main()
{
    int n,i,k,kk;
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    k=2;
    sts[1]=v[1];
    sts[2]=v[2];
    for(i=3;i<=n;i++)
    {
        while(k>=2&&crb(sts[k-1],sts[k],v[i])==false)
        {
            k--;
        }
        k++;
        sts[k]=v[i];
    }
    stdr[1]=v[n];
    stdr[2]=v[n-1];
    kk=2;
    for(i=n-2;i>=1;i--)
    {
        while(kk>=2&&crb(stdr[kk-1],stdr[kk],v[i])==false)
        {
            kk--;
        }
        kk++;
        stdr[kk]=v[i];
    }
    out<<setprecision(6)<<fixed;
    out<<kk+k-2<<'\n';
    for(i=1;i<=k;i++)
    {
        out<<sts[i].x<<" "<<sts[i].y<<'\n';
    }
    for(i=2;i<kk;i++)
        out<<stdr[i].x<<" "<<stdr[i].y<<'\n';
}