Cod sursa(job #3268064)

Utilizator Victor5539Tanase Victor Victor5539 Data 13 ianuarie 2025 16:38:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int MAX=12e4;
int n,i;
stack <int> s;

struct elem{
double x,y;}v[MAX+5];

double abs(double x)
{
    if (x<=0)
        return -x;

    return x;
}

double determinant(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
}

bool compare(elem a, elem b)
{
    if (a.x!=b.x)
        return a.x<b.x;

    return a.y<b.y;
}

bool unghi(elem a, elem b, elem c)
{
    return determinant(a.x,a.y,b.x,b.y,c.x,c.y)<0;
}

bool compare2(elem a, elem b)
{
    return unghi(v[1],a,b);
}


int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,compare);

    s.push(1);
    sort(v+2,v+n+1,compare2);

    s.push(2);

    for (i=3; i<=n; i++)
    {
        while (s.size()>=2)
        {
            int ind1=s.top();
            s.pop();
            int ind2=s.top();

            double x1=v[ind2].x, y1=v[ind2].y, x2=v[ind1].x, y2=v[ind1].y, x3=v[i].x, y3=v[i].y;

            if (determinant(x1,y1,x2,y2,x3,y3)<=0)
            {
                s.push(ind1);
                break;
            }
        }

        s.push(i);
    }

    fout<<s.size()<<"\n";
    while (!s.empty())
    {
        fout<<fixed<<setprecision(6)<<v[s.top()].x<<" "<<v[s.top()].y<<"\n";
        s.pop();
    }
    return 0;
}