Cod sursa(job #2935376)

Utilizator gabriela.stanStan Luciana-Gabriela gabriela.stan Data 6 noiembrie 2022 17:02:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
#define NMAX 120002
using namespace std;

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

struct punct
{
    long double x;
    long double y;
}p[NMAX];

enum Orientare
{
    CLOCKWISE,
    COUNTERCW,
    COLINIARE
};

Orientare orientare(punct A, punct B, punct C)
{
    long double det=(A.y-B.y)*(C.x-B.x)-(A.x-B.x)*(C.y-B.y);
    if(det<0) return CLOCKWISE;
    if(det>0) return COUNTERCW;
    return COLINIARE;
}

bool comp(punct A, punct B)
{
    if(A.x==B.x)
    {
        return (B.y>A.y);
    }
    else return (B.x>A.x);
}

int n;
vector <punct> v1;
vector <punct> v2;

void jum1()
{
    v1.push_back(p[0]);
    v1.push_back(p[1]);
    for(int i=2; i<n; i++)
    {
        v1.push_back(p[i]);
        int s=v1.size()-1;
        while(s>1 && orientare(v1[s-2], v1[s-1], v1[s])==CLOCKWISE)
        {
            v1.erase(v1.begin()+s-1);
            s--;
        }
    }
}
void jum2()
{
    v2.push_back(p[n-1]);
    v2.push_back(p[n-2]);
    for(int i=n-3; i>=0; i--)
    {
        v2.push_back(p[i]);
        int s=v2.size()-1;
        while(s>1 && orientare(v2[s-2], v2[s-1], v2[s])==CLOCKWISE)
        {
            v2.erase(v2.begin()+s-1);
            s--;
        }
    }
}

int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
    {
        fin>>p[i].x>>p[i].y;
    }
    sort(p, p+n, comp);
    jum1();
    jum2();
    int s1=v1.size(), s2=v2.size();
    fout<<s1+s2-2<<'\n';
    for(int i=0; i<s1-1; i++)
    {
        fout<<fixed<<setprecision(6)<<v1[i].x<<" ";
        fout<<fixed<<setprecision(6)<<v1[i].y<<'\n';
    }
    for(int i=0; i<s2-1; i++)
    {
        fout<<fixed<<setprecision(6)<<v2[i].x<<" ";
        fout<<fixed<<setprecision(6)<<v2[i].y<<'\n';
    }
    return 0;
}