Cod sursa(job #2659615)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 17 octombrie 2020 11:12:13
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#define NMAX 120005
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point{
    double x = 0, y = 0;
}P[NMAX];

int n;
vector<point> v1, v2;

bool cmp(point A, point B)
{
    if(A.x < B.x || A.x == B.x && A.y < B.y)
        return 1;
    return 0;
}



void read()
{
    f>>n;
    for(int i = 1; i <= n; ++i)
        f>>P[i].x>>P[i].y;
    sort(P+1, P+n+1, cmp);
}

double determinant(point P1, point P2, point P3)
{
    return (P2.x - P1.x)*(P3.y - P1.y) - (P2.y - P1.y)*(P3.x - P1.x);
}

void write()
{
    g<<v1.size() + v2.size() - 2<<'\n';
    for(auto &v:v1)
        g<<fixed<<setprecision(6)<<v.x<<" "<<v.y<<"\n";
    for(int i = 1; i < v2.size()-1; ++i)
        g<<fixed<<setprecision(6)<<v2[i].x<<" "<<v2[i].y<<"\n";
}



void solve()
{
    v1.push_back(P[1]);
    v1.push_back(P[2]);
    for(int i = 3; i <= n; ++i)
    {
        if(v1.size() <= 1)
            v1.push_back(P[i]);
        else{
            while(v1.size() > 1 && determinant(v1[v1.size()-2], v1[v1.size()-1], P[i]) < 0)
                v1.pop_back();
            v1.push_back(P[i]);
        }
    }
    v2.push_back(P[n]);
    v2.push_back(P[n-1]);
    for(int i = n-2; i >= 1; --i)
    {
        if(v1.size() <= 1)
            v2.push_back(P[i]);
        else{
            while(v1.size() > 1 && determinant(v2[v2.size()-2], v2[v2.size()-1], P[i]) < 0)
                v2.pop_back();
            v2.push_back(P[i]);
        }
    }

}


int main()
{
    read();
    solve();
    write();
    return 0;
}