Cod sursa(job #2987265)

Utilizator VenomPool9Bogdan VenomPool9 Data 2 martie 2023 10:09:47
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;
struct point {double x,y;};
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N;
point P[120001];
deque <int> DR;
deque <int> ST;
/// return 1 if and only if C is to the left of AB
int left(point A, point B, point C)
{
    double det;
    det=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
    if (det>0)
        return 1;
    else
        return 0;
}

int cmp(point A, point B)
{
    if (A.y<B.y)
        return 1;
    if (A.y>B.y)
        return 0;
    return (A.x<B.x);
}

int main()
{
    fi>>N;
    for (int i=1;i<=N;i++)
        fi>>P[i].x>>P[i].y;
    sort(P+1,P+N+1,cmp);
    /// DR is obtained
    for (int i=1;i<=N;)
        if (DR.size()<2)
        {
            DR.push_back(i);
            i++;
        }
        else
        {
            int indA,indB;
            point A,B;
            indB=DR.back();
            DR.pop_back();
            indA=DR.back();
            DR.pop_back();
            A=P[indA];
            B=P[indB];
            if (left(A,B,P[i]))
            {
                DR.push_back(indA);
                DR.push_back(indB);
                DR.push_back(i);
                i++;
            }
            else
                DR.push_back(indA);
        }
    /// ST is obtained
    for (int i=N;i>=1;)
        if (ST.size()<2)
        {
            ST.push_back(i);
            i--;
        }
    else
        {
            int indA,indB;
            point A,B;
            indB=ST.back();
            ST.pop_back();
            indA=ST.back();
            ST.pop_back();
            A=P[indA];
            B=P[indB];
            if (left(A,B,P[i]))
            {
                ST.push_back(indA);
                ST.push_back(indB);
                ST.push_back(i);
                i--;
            }
            else
                ST.push_back(indA);
        }
    ST.pop_front();
    ST.pop_back();
    fo<<DR.size()+ST.size()<<"\n";
    for (auto it:DR)
        fo<<P[it].x<<" "<<P[it].y<<"\n";
    for (auto it:ST)
        fo<<P[it].x<<" "<<P[it].y<<"\n";
    fi.close();
    fo.close();
    return 0;
}