Cod sursa(job #3349122)

Utilizator TeodorVTeodorV TeodorV Data 25 martie 2026 16:41:42
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

const string NUMEFISIER="infasuratoare";
ifstream fin(NUMEFISIER+".in");
ofstream fout(NUMEFISIER+".out");


int main()
{
    int n;
    fin>>n;
    vector<pair<double, double>> v(n);
    int startPoint=0;
    for(int i=0; i<n; i++)
    {
        fin>>v[i].first>>v[i].second;
        if(v[startPoint].second<v[i].second)
            startPoint=i;
    }

    vector<int> convexHull;
    vector<bool> visited(n);

    int currentPoint=startPoint;
    bool first=1;
    double lastAngle=0;
    while(startPoint!=currentPoint || first)
    {
        first=0;
        convexHull.push_back(currentPoint);

        double maxAngle=-1; int newPoint=currentPoint;
        for(int i=0; i<n; i++)
        {
            if(i==currentPoint || visited[i]) continue;

            double angle=atan2(v[i].second-v[currentPoint].second,v[i].first-v[currentPoint].first);
            if(angle<0) angle+=2.0*M_PI;
            angle-=lastAngle;
            if(angle<0) angle+=2.0*M_PI;
            if(maxAngle<angle)
            {
                maxAngle=angle;
                newPoint=i;
            }
        }
        lastAngle=atan2(v[newPoint].second-v[currentPoint].second,v[newPoint].first-v[currentPoint].first);
        if(lastAngle<0) lastAngle+=2.0d*M_PI;

        currentPoint=newPoint;
        visited[currentPoint]=1;
    }
    fout<<convexHull.size()<<'\n';
    for(int i=convexHull.size()-1; i>=0; i--)
        fout<<v[convexHull[i]].first<<' '<<v[convexHull[i]].second<<'\n';

    return 0;
}