Cod sursa(job #1796672)

Utilizator andru47Stefanescu Andru andru47 Data 3 noiembrie 2016 17:45:31
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define punct pair <double,double>
#define x first
#define y second
#define eps 10e-12
using namespace std;
const int NMAX = 120000 + 5;
punct a[NMAX];
vector <int> v;
bool inside[NMAX];
int n;
int comper(double a,double b)
{
    if (a+eps<b)return -1;
    else if(b+eps<a)return 1;
    return 0;
}
int compare(punct a,punct b,punct c)
{
    double determinant = a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
    return comper(determinant,0);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d\n", &n);
    for (int i = 1; i<=n; ++i)
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
    sort(a+1,a+n+1);
    v.push_back(1);
    v.push_back(2);
    inside[2] = true;
    int actual = 3;
    int pluS = 1;
    int in = 2;
    while(!inside[1])
    {
        if (inside[actual])
        {
            if (actual==n)
                pluS = -1;
            actual+=pluS;
        }
            while(in>=2&&compare(a[v[in-2]],a[v[in-1]],a[actual])==1)
                inside[v[in-1]] = false,v.pop_back(),--in;

        inside[actual] = true;
        v.push_back(actual);
        ++in;
    }
    v.pop_back();
    printf("%d\n", v.size());
    reverse(v.begin(),v.end());
    for (auto &it : v)
        printf("%f %f\n",a[it].x,a[it].y);
    return 0;
}