Cod sursa(job #2878117)

Utilizator alexxxxxxhalex alx alexxxxxxh Data 25 martie 2022 20:27:54
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct p
{
    double x,y;
};
p v[120001];
double cmp(p a,p b)
{
    if (a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
double calc(double xa,double ya,double xb,double yb, double xc,double yc)
{
    return (xa*yb+xb*yc+xc*ya-yc*xa-yb*xc-xb*ya)/2.0;
}
int n;
p stiva[120001];
p stiva1[120001];
int k;
int k1;
int  main()
{
    fin >>n;
    for (int i=1; i<=n; i++)
    {
        fin >>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    int i=2;
    stiva[++k].x=v[1].x;
    stiva[k].y=v[1].y;
    while (i<=n)
    {
        if (k<2)
        {
            if (calc(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y)<0)
            {
                stiva[++k].x=v[i].x;
                stiva[k].y=v[i].y;
            }
        }
        else
        {
            while (calc(stiva[k-1].x,stiva[k-1].y,stiva[k].x,stiva[k].y,v[i].x,v[i].y)<0 && k>=2)
            {
                k--;
            }
            stiva[++k].x=v[i].x;
            stiva[k].y=v[i].y;
        }
        i++;
    }

    i=1;
    stiva1[++k1].x=v[1].x;
    stiva1[k1].y=v[1].y;
    while (i<=n)
    {
        if (k1<2)
        {
            if (calc(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y)>0)
            {
                stiva1[++k1].x=v[i].x;
                stiva1[k1].y=v[i].y;
            }
        }
        else
        {
            while (calc(stiva1[k1-1].x,stiva1[k1-1].y,stiva1[k1].x,stiva1[k1].y,v[i].x,v[i].y)>0 && k1>=2)
            {
                k1--;
            }
            stiva1[++k1].x=v[i].x;
            stiva1[k1].y=v[i].y;
        }
        i++;
    }
    fout << k1+k-2 <<"\n";
    fout << v[1].x <<" "<<v[1].y <<"\n";
    for (int j=2; j<=k-1; j++) fout << stiva[j].x <<" "<<stiva[j].y<<"\n";
    fout <<v[n].x <<" "<<v[n].y<<"\n";
    for (int j=k1-1; j>=2; j--) fout << stiva1[j].x <<" "<<stiva1[j].y<<"\n";
    fout <<"\n";
}