Cod sursa(job #3246410)

Utilizator sebigabiSebastian Itu sebigabi Data 2 octombrie 2024 22:10:55
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define pff pair<float, float>
using namespace std;

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

const int NMAX = 120000 + 1;
int n;

bool cmp_cresc(const pff& a, const pff& b)
{
    if(a.first < b.first)
    {
        return 1;
    }
    if(a.first == b.first)
    {
        return a.second < b.second;
    }
    if(a.first > b.first)
    {
        return 0;
    }
    return 0;
}

float arie(pff A, pff B, pff C)
{
    return (A.first * B.second + B.first * C.second + C.first * A.second)
           -(C.first * B.second + A.first * C.second + B.first * A.second);
}

int semn(pff A, pff B, pff C)
{
    float area = arie(A, B, C);

    if(area > 0) //sus sau stanga
    {
        return 1;
    }
    if(area < 0) //jos sau dreapta
    {
        return -1;
    }

    return 0; //apartine AB
}

//void afis_vector(vector<pff> sir)
//{
//    int marime = sir.size();
//    for(int i=marime-1; i>=0; i--)
//    {
//        out<<fixed<<setprecision(6)<<sir[i].first<<" "<<sir[i].second<<"\n";
//    }
//    out<<"\n";
//}

int main()
{
    in>>n;

    vector<pff> v;
    for(int i=1; i<=n; i++)
    {
        float x,y;
        in>>x>>y;
        v.push_back(make_pair(x, y));
    }
    sort(v.begin(), v.end(), cmp_cresc);
    //afis_vector(v);

    pff left_limit = v[0];
    pff right_limit = v[n-1];

    vector<int> stiva;
    stiva.push_back(0);

    for(int i=1; i<n; i++)
    {
        if(semn(left_limit, right_limit, v[i]) == -1)
        {
            while(stiva.size() >= 2 && semn(v[stiva[stiva.size()-2]], v[stiva.back()], v[i]) == -1)
            {
                stiva.pop_back();
            }
            stiva.push_back(i);
        }
    }
    int marime = stiva.size();

    stiva.push_back(n-1);
    for(int i=n-2; i>=0; i--)
    {
        if(semn(left_limit, right_limit, v[i]) == 1)
        {
            while(stiva.size() > marime && semn(v[stiva[stiva.size()-2]], v[stiva.back()], v[i]) == -1)
            {
                stiva.pop_back();
            }
            stiva.push_back(i);
        }
    }

    marime = stiva.size();

    out<<marime<<"\n";
    for(int i=0; i<marime; i++)
    {
        out<<v[stiva[i]].first<<" "<<v[stiva[i]].second<<"\n";
    }
    return 0;
}