Cod sursa(job #3186235)

Utilizator Darius1414Dobre Darius Adrian Darius1414 Data 22 decembrie 2023 10:50:55
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <iomanip>
#define nmx 120005
using namespace std;
int n,i2;
double xm,ym,x,y;
struct edge
{
    double x,y;
};
vector <edge> v;
bool cmp(edge a,edge b)
{
    return ((a.y-ym)*(b.x-xm)<(a.x-xm)*(b.y-ym));
}
deque <edge> dq;
bool orientation(edge a,edge b,edge c)
{
    double nr=a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
    if (nr>0) return 1;
    return 0;
}
int main()
{
    ifstream f ("infasuratoare.in");
    ofstream g ("infasuratoare.out");
    f>>n;
    ym=1000000005;
    for (int i=1; i<=n; i++)
    {
        f>>x>>y;
        if (y<ym)
        {
            ym=y;
            xm=x;
            i2=i;
        }
        v.push_back({x,y});
    }
    for (int i=0;i<n;i++)
        if (v[i].x==xm && v[i].y==ym) swap(v[0],v[i]);
    sort (v.begin()+1,v.end(),cmp);
    dq.push_front(v[0]);
    dq.push_front(v[1]);
    for (int i=2; i<n; i++)
    {
        edge a,b,c;
        c=v[i];
        b=dq.front();
        dq.pop_front();
        a=dq.front();
        if (orientation(a,b,c))
        {
            cout<<i<<' ';
            dq.push_front(b);
            dq.push_front(c);
        }
        else
        {
            dq.push_front(c);
        }
    }
    g<<dq.size()<<'\n';
    g<<fixed<<setprecision(6);
    while (dq.size()>0)
    {
        auto u=dq.back();
        dq.pop_back();
        g<<u.x<<' '<<u.y<<'\n';
    }
}