Cod sursa(job #3247535)

Utilizator DanSerbanDan Serban DanSerban Data 8 octombrie 2024 11:19:04
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stack>
using namespace std;
stack<int> varf;
int n;
const double t=1000000000.;
struct coordonate
{
    double X;
    double Y;
    ///short verif=0;
}cuie[120000];
bool compareCoordinates(coordonate a, coordonate b)
{
    if(a.X!=b.X)
        return a.X<b.X;
    if(a.Y!=b.Y)
        return a.Y<b.Y;
}

double arie(coordonate a, coordonate b, coordonate c)
{
    double A=a.X*b.Y+b.X*c.Y+c.X*a.Y-c.X*b.Y-a.X*c.Y-b.X*a.Y;
    return A;
}

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin>>n;
    for(int i=0; i<n; ++i)
    {
        fin>>cuie[i].X>>cuie[i].Y;
        cutie[i].X+=t;
        cutie[i].Y+=t;
    }

    sort(cuie, cuie+n, compareCoordinates);

    int ok;
    varf.push(0);
    ///cuie[0].verif=1;
    varf.push(1);
    if(arie(cuie[0], cuie[n-1], cuie[1])>=0.)
        ok=1;
    else
        ok=-1;
    ///cuie[1].verif=1;
    for(int i=2; i<n-1; ++i)
    {
        if(arie(cuie[0], cuie[n-1], cuie[i])*ok>=0.)
        {
            while(arie(cuie[varf[varf.size()-2]], cuie[varf[varf.size()-1]], cuie[i])*ok>=0.)
            {
                varf.pop();
                if(varf.size()<2)
                    break;
            }
            varf.push(i);
        }
        ///cuie[i].verif=1;
    }
    varf.push(n-1);

    for(int i=2; i<n-1; ++i)
    {
        if(arie(cuie[0], cuie[n-1], cuie[i])*ok<0.)
        {
            while(arie(cuie[varf[varf.size()-2]], cuie[varf[varf.size()-1]], cuie[i])*ok>=0.)
            {
                varf.pop();
                if(varf.size()<2)
                    break;
            }
            varf.push(i);
        }
        ///cuie[i].verif=1;
    }
    /*for(int i=0; i<n; ++i)
        cout<<cuie[i].X<<' '<<cuie[i].Y<<'\n';*/
    fin.close();
    fout.close();
    return 0;
}