Cod sursa(job #2542999)

Utilizator Catalin_GriuGriu Catalin Catalin_Griu Data 10 februarie 2020 19:29:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
#define ld long double
#define pdd pair<ld, ld>
using namespace std;

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

int n;
ld x, y, m;
vector<pdd>v;
vector<pdd> s;
pdd p1, p2, st;

ld det(pdd p1, pdd p2, pdd p3)
{
    ld x1 = p1.first, x2 = p2.first, x3 = p3.first;
    ld y1 = p1.second, y2 = p2.second, y3 = p3.second;
    return(x1*y2+y1*x3+x2*y3-y2*x3-y1*x2-y3*x1);
}
void alg(int from)
{
    for(int i=from; i<n; i++)
    {
        if(v[i]==st)
            continue;
        while(det(p1, p2, v[i])>0)
        {
            s.pop_back();
            p2 = p1;
            p1 = s[s.size()-2];
        }
        p1 = p2;
        p2 = v[i];
        s.push_back(v[i]);
    }
}

bool cmp(pdd p1, pdd p2)
{
    if(st.first-p1.first==0)
        return true;
    if(st.first-p2.first==0)
        return false;
    if((st.second-p1.second)/(st.first-p1.first) > (st.second-p2.second)/(st.first-p2.first ))
        return true;
    return false;
}

int main()
{
   fin>>n;
   st.first = 1000000009;
   st.second = 1000000009;
   for(int i=1; i<=n; i++)
   {
       fin>>x>>y;
       v.push_back(make_pair(x, y));
       if(x<st.first)
       {
           st.first = x;
           st.second = y;
       }
       else if(x==st.first&&y<st.second)
            st.second = y;
   }

   sort(v.begin(), v.end(), cmp);
    s.push_back(st);
    p1 = st;
    if(v[0]!=st)
    {
        s.push_back(v[0]);
        p2 = v[0];
        alg(1);
    }
    else
    {
        s.push_back(v[1]);
        p2 = v[1];
        alg(2);
    }
    fout<<s.size()<<'\n';
    for(auto i:s)
        fout<<i.first<< ' '<<i.second<<'\n';

    return 0;
}