Cod sursa(job #2362078)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 2 martie 2019 21:47:27
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 120005

using namespace std;

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

const double EPS=1e-12;
int n;
pair <double, double> v[Nmax];
bool used[Nmax];
int st[Nmax], top=2;

double det(int a, int b, int c)
{
    double ax=v[a].first, ay=v[a].second;
    double bx=v[b].first, by=v[b].second;
    double cx=v[c].first, cy=v[c].second;
    double ans=0;
    ans+=ax*by;
    ans+=bx*cy;
    ans+=cx*ay;
    ans-=cx*by;
    ans-=ax*cy;
    ans-=bx*ay;

    return ans;
}

int main(){

    f >> n;
    for (int i = 1; i <= n; i++){
        double x, y;
        f >> x >> y;
        v[i]={x, y};
    }
    sort(v+1, v+n+1);
    st[1]=1;
    st[2]=2;
    used[1]=used[2]=1;
    for (int i = 3; i <= n; i++)
    {
        while(top >= 2 && det(st[top], st[top-1], i) < EPS)
        {
            used[st[top]]=0;
            top--;
        }
        top++;
        used[i]=1;
        st[top]=i;
    }

    for (int i = n-1; i >= 1; i--)
    {
        if(used[i] == 1) continue;
        while(top >= 2 && det(st[top], st[top-1], i) < EPS)
        {
            used[st[top]]=0;
            top--;
        }
        top++;
        st[top]=i;
        used[i]=1;
    }

    top--;
    g << top << '\n';

    for (int i = top; i >= 1; i--)
        g << fixed << setprecision(12) << v[st[i]].first << " " << fixed << setprecision(12) << v[st[i]].second << '\n';

    return 0;
}