Cod sursa(job #2410107)

Utilizator PredaBossPreda Andrei PredaBoss Data 19 aprilie 2019 18:50:12
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
ld x,y;
const ld PI=3.14159265359;
pair<pair<ld,ld>,int> mn;
vector<pair<ld,ld> >elem;
vector<int>v;
vector<int>ans;
bool cmp(int a,int b)
{
    return (elem[a].first-x)*(elem[b].second-y)>(elem[a].second-y)*(elem[b].first-x);
}
ld det(int a,int b,int c)
{
    return elem[a].first*elem[b].second+elem[a].second*elem[c].first+elem[b].first*elem[c].second-elem[c].first*elem[b].second-elem[a].first*elem[c].second-elem[a].second*elem[b].first;
}
void solve()
{
    ans.push_back(v[0]);
    int k=1;
    if(y<elem[0].second)
        k=-1;
    int it=0;
    for(int i=1;i<n-1;i++)
    {
        while(k*det(ans[it],ans[it+1],v[i])<=0)
        {
            it--;
            ans.pop_back();
        }
        it++;
        ans.push_back(v[i]);
    }
    fout<<setprecision(12)<<fixed;
    fout<<ans.size()<<"\n";
    for(auto it:ans)
        fout<<elem[it].first<<" "<<elem[it].second<<"\n";
}
int main()
{
    fin>>n;
    mn={{INT_MAX,INT_MAX},INT_MAX};
    for(int i=0;i<n;i++)
    {
        fin>>x>>y;
        mn=min(mn,{{y,x},i});
        elem.push_back({x,y});
    }
    int pos=mn.second;
    y=mn.first.first;
    x=mn.first.second;
    for(int i=0;i<n;i++)
        if(i!=pos)
            v.push_back(i);
    sort(v.begin(),v.end(),cmp);
    ans.push_back(pos);
    solve();
    return 0;
}