Cod sursă (job #646690)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int xmin=INT_MAX,ymin=INT_MAX;

struct comp{
    bool operator()(const pair<int,int> &a, const pair<int,int> &b) const{
        return acos(((a.first-xmin))/(1.0*(sqrt(pow(a.first-xmin,2)+pow(a.second-ymin,2)))))>acos((1.0*(b.first-xmin))/(1.0*(sqrt(pow(b.first-xmin,2)+pow(b.second-ymin,2)))));
    }
};


priority_queue<pair<int,int>,vector<pair<int,int>>,comp> pq;
vector<pair<int,int>>v;

string intoarcere(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3)
{
    double val=(p3.second-p2.second)*(p2.first-p1.first)-(p2.second-p1.second)*(p3.first-p2.first);
    if(val>0)
    return "intoarcere_stanga";
    else if(val==0){
        return "coliniar";
    }else
        return "intoarcere_dreapta";

}

double distanta(pair<int,int> a,pair<int,int> b){
    return sqrt(pow(a.first-b.first,2)+pow(a.second-b.second,2));
}

int main()
{
    int n;
    fin>>n;
    int ind;
    for(int i=0;i<n;i++){
        int a,b;
        fin>>a>>b;
        v.push_back({a,b});
        if(b<ymin){
            ind=i;
            xmin=a;
            ymin=b;
        }else if(b==ymin && a<xmin){
            ind=i;
            xmin=a;
            ymin=b;
        }
    }

    v.erase(v.begin()+ind,v.begin()+ind+1);
    for(auto it:v){
        pq.push(it);
    }

    vector<pair<int,int>> hull;
    hull.push_back({xmin,ymin});
    hull.push_back({pq.top().first,pq.top().second});
    pq.pop();

    while(!pq.empty()){
        string query=intoarcere(hull[hull.size()-2],hull[hull.size()-1],pq.top());

        while(hull.size()>2 && query=="intoarcere_dreapta")
        {
            hull.pop_back();
            query=intoarcere(hull[hull.size()-2],hull[hull.size()-1],pq.top());
        }
        if(query=="intoarcere_stanga")
        {
            hull.push_back(pq.top());
        }else if(query=="coliniar"){
            if(distanta(hull[hull.size()-2],hull[hull.size()-1])<distanta(hull[hull.size()-2],pq.top())){
                    hull.pop_back();
                    hull.push_back(pq.top());
            }
        }
        pq.pop();
    }
    string query=intoarcere(hull[hull.size()-2],hull[hull.size()-1],{xmin,ymin});
    if(query=="intoarcere_dreapta")
        hull.pop_back();
    else if(query=="coliniar"){
        if(distanta(hull[hull.size()-2],{xmin,ymin})>distanta(hull[hull.size()-1],{xmin,ymin}))
            {
                hull.pop_back();
            }
    }
    fout<<hull.size()<<'\n';
    for(auto it:hull){
        fout<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}