Cod sursa(job #2890027)

Utilizator valentina_veleatVeleat Valentina-Georgiana valentina_veleat Data 14 aprilie 2022 10:15:05
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.78 kb
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-12
const double INF = 1e18;
const int nmax=100005;
ifstream f("text.in");
ofstream g("text.out");
struct punct  //structura de date pentru a reprezenta un punct in plan
{
    double X, Y;
};
punct v[nmax];
int s[nmax],ok[nmax];
struct cerc  //structura de date pentru a reprezenta un cerc in plan
{
    punct C;
    double R;
};
double distanta(punct& a, punct& b)//functie ce returneaza distanta dintre doua puncte in plan
{
    return sqrt(pow(a.X - b.X, 2)+ pow(a.Y - b.Y, 2));
}
bool valid(cerc& c, punct& p)//functie ce returneaza true sau false daca punctul este in interiorul cercului, respectiv pe marginea acestuia
{
    return distanta(c.C, p) <= c.R;
}
punct centrucerc(double bx, double by, double cx, double cy)//functie ce returneaza centrul cercului definit de 3 puncte
{
    double B = bx * bx + by * by;
    double C = cx * cx + cy * cy;
    double D = bx * cy - by * cx;
    return { (cy * B - by * C) / (2 * D),(bx * C - cx * B) / (2 * D) };
}
cerc cerc3( punct& A, punct& B, punct& C)//functie ce returneaza un cerc unic ce intersecteaza 3 puncte
{
    punct I = centrucerc(B.X - A.X, B.Y - A.Y,C.X - A.X, C.Y - A.Y);
    I.X += A.X;
    I.Y += A.Y;
    return { I, distanta(I, A) };
}
cerc cerc2( punct& A, punct& B)//functie ce returneaa cel mai mic cerc ce intersecteaza 2 puncte
{
    punct C = { (A.X + B.X) / 2.0, (A.Y + B.Y) / 2.0 };// centrul este mijlocul segementului AB
    return { C, distanta(A, B) / 2.0 };// raza este 1/2 din lungimea segmentului AB
}
bool cercvalid(cerc& c,vector<punct>& P)//functie ce verifica daca cercul contine punctele date
{
    for(punct& p : P)
        if (!valid(c, p))
            return false;
    return true;
}
cerc cercminim(vector<punct>& P)//functie ce returneaza cercul minim pentru n<=3
{
    assert(P.size() <= 3);
    //{
    if (P.empty())
    {
        return { { 0, 0 }, 0 };
    }
    else if (P.size() == 1)
    {
        return { P[0], 0 };
    }
    else if (P.size() == 2)
    {
        return cerc2(P[0], P[1]);
    }
    for (int i = 0; i < 3; i++)  //verficam daca cercul minim poate fi determinat de 2 puncte
    {
        for (int j = i + 1; j < 3; j++)
        {
            cerc c = cerc2(P[i], P[j]);
            if (cercvalid(c, P))
                return c;
        }
    }
    return cerc3(P[0], P[1], P[2]);
    //}
}
// n e numarul de puncte care nu au fost parcurse pana acum
cerc solve(vector<punct>& P,vector<punct> R, int n)//setul R contine puncte de pe circumferinta cercului
{
    if (n == 0 || R.size() == 3) //cazul de baza cand toate punctele au fost procesate sau R contine 3 puncte
    {
        return cercminim(R);
    }
    int idx = rand() % n;//alegem un punct la intamplare
    punct p = P[idx];
    swap(P[idx], P[n - 1]);
    cerc d = solve(P, R, n - 1);//obtinem cercul minim din setul P excluzand punctul p
    if (valid(d, p))
    {
        //daca d il contine pe p, returnam d
        return d;
    }
    R.push_back(p);//altfel, p se afla pe circumferinta cercului
    return solve(P, R, n - 1);// returnam cercul minim pentru P-{p} si R U {p}
}
int cmp1(double a,double b)
{
    if (a+eps<b) return 1;
    if (b+eps<a) return -1;
    return 0;
}
bool cmp(punct &a, punct &b)//functia de comparare a cooordonatelor
{
    int t;
    t=cmp1(a.X,b.X);
    if (t!=0) return t==1;
    return (cmp1(a.Y,b.Y)==1);
}
int semn(punct a,punct b,punct c) //se verifica daca C nu apartine dreptei AB
{
    double A,B,C;
    A = a.Y-b.Y;
    B = b.X-a.X;
    C = a.X*b.Y - b.X*a.Y;
    return cmp1(A*c.X+B*c.Y+C,0);
}
int n,h,i;
void solve2()
{
    int k,q;
    sort(v+1,v+n+1,cmp);
    s[1]=1;
    s[2]=2; //in stiva s se introduce cel mai din stanga punct si cel de-al doilea care urmeaza sa fie verificat
    ok[2]=1;
    k=2;
    i=3;
    q=1;
    while (!ok[1])
    {
        while(ok[i])
        {
            if(i==n)q=-1;
            i+=q;
        }
        while(k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
        {
            ok[s[k--]]=0;
        }
        s[++k]=i;
        ok[i]=1;
    }
    h=k-1;
}
int c;
punct w;
vector <punct> P;
int main()
{
    //f>>c;
    c=2;
    f>>n;
    if(c==1)
    {
        for(int i=1; i<=n; i++)
        {
            f>>w.X>>w.Y;
            P.push_back(w);
        }
        vector<punct> P_copy = P;
        cerc cm=solve(P_copy, {}, P_copy.size());
        g<<cm.C.X <<" "<< cm.C.Y<< " "<<cm.R << endl;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            f>>v[i].X>>v[i].Y;
        }
        solve2();
        g<<h;
        g<<fixed<<setprecision(12);
        for(int i=2; i<=h+1; i++)
        {
            g<<v[s[i]].X<<" "<<v[s[i]].Y<<'\n';
        }
    }
    return 0;
}