Cod sursa(job #3327258)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 2 decembrie 2025 22:34:02
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.81 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;

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

struct point{
    double x,y;
}p[120005];

int cresc(point a,point b)
{
    if(a.x<b.x)
    return 1;
    else if(a.x==b.x)
    {
        if(a.y<b.y)
        return 1;
    }
    return 0;
}
int decresc(point a,point b)
{
    if(a.x>b.x)
    return 1;
    else if(a.x==b.x)
    {
        if(a.y>b.y)
        return 1;
    }
    return 0;
}
deque <pair<double,double>> to_dr;
deque <pair<double,double>> to_st;

int n;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>p[i].x>>p[i].y;
    }
    sort(p+1,p+n+1,cresc);
    to_st.push_front(make_pair(p[1].x,p[1].y));
    to_st.push_front(make_pair(p[2].x,p[2].y));
    for(int i=3;i<=n;i++)
    {
        double det=0;
        do{
        double xb=to_st.front().first;
        double yb=to_st.front().second;
        to_st.pop_front();
        double xa=to_st.front().first;
        double ya=to_st.front().second;
        to_st.push_front(make_pair(xb,yb));
        double xc=p[i].x;
        double yc=p[i].y;
        det=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
        //cout<<xa<<" "<<ya<<endl<<xb<<" "<<yb<<endl<<xc<<" "<<yc<<endl<<det<<endl<<endl;
        if(det==0)
        {
            to_st.pop_front();
        }
        else if (det<0)
        {
             to_st.pop_front();
        }
        }while(det<0 && to_st.size()>1);
        to_st.push_front(make_pair(p[i].x,p[i].y));
    }
    sort(p+1,p+n+1,decresc);
    to_dr.push_front(make_pair(p[1].x,p[1].y));
    to_dr.push_front(make_pair(p[2].x,p[2].y));
    for(int i=3;i<=n;i++)
    {
        double det=0;
        do{
        double xb=to_dr.front().first;
        double yb=to_dr.front().second;
        to_dr.pop_front();
        double xa=to_dr.front().first;
        double ya=to_dr.front().second;
        to_dr.push_front(make_pair(xb,yb));
        double xc=p[i].x;
        double yc=p[i].y;
        det=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
        //cout<<xa<<" "<<ya<<endl<<xb<<" "<<yb<<endl<<xc<<" "<<yc<<endl<<det<<endl<<endl;
        if(det==0)
        {
            to_dr.pop_front();
        }
        else if(det<0)
        {
             to_dr.pop_front();
        }
        }while(det<0 && to_dr.size()>1);
        to_dr.push_front(make_pair(p[i].x,p[i].y));
    }
    fout<<to_dr.size()+to_st.size()-2<<"\n";
    while(!to_dr.empty())
    {
        fout<<to_dr.back().first<<" "<<to_dr.back().second<<"\n";
        to_dr.pop_back();
    }
    to_st.pop_back();
    to_st.pop_front();
    while(!to_st.empty())
    {
        fout<<to_st.back().first<<" "<<to_st.back().second<<"\n";
        to_st.pop_back();
    }
    return 0;
}