Cod sursa(job #2557872)

Utilizator mihaela.macarie01@yahoo.comMihaela Macarie [email protected] Data 26 februarie 2020 09:15:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#define N 120002
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream x("infasuratoare.in");
ofstream y("infasuratoare.out");

int n,ok,s[N];
bool viz[N];

struct elem
{
    double xx,yy;
}v[N];

bool cmp(elem a, elem b)
{
    if(a.xx==b.xx)
        return a.yy<b.yy;
    return a.xx<b.xx;
}

double det(elem A, elem B, elem C)
{
    double a=A.xx,b=A.yy,c=B.xx,d=B.yy,e=C.xx,f=C.yy;
    double delta=a*d+c*f+e*b-d*e-a*f-c*b;
    return delta;
}

void rezolvare(int n, int &top)
{
    int ok=1,i;
    s[1]=1;
    s[2]=2;
    viz[2]=1;
    top=2;
    i=3;
    while(!viz[1])
    {
        while(viz[i])
        {
            if(i==n)
                ok=-1;
            i+=ok;
        }
        while(det(v[s[top-1]],v[s[top]],v[i])<0 && top>=2)
            viz[s[top]]=0,top--;
        s[++top]=i;
        viz[i]=1;
    }
    top--;
}

int main()
{
    x>>n;
    int top;
    for(int i=1;i<=n;i++)
        x>>v[i].xx>>v[i].yy;
    sort(v+1,v+n+1,cmp);
    rezolvare(n,top);
    y<<top<<'\n';
    for(int i=2;i<=top+1;i++)
        y<<fixed<<setprecision(6)<<v[s[i]].xx<<" "<<v[s[i]].yy<<'\n';
    x.close();
    y.close();
    return 0;
}