Cod sursa(job #1509834)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 24 octombrie 2015 12:37:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

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

const int nmax=120005;
struct punct {double x,y;};
punct a[nmax];
punct stiv1[nmax];
punct stiv2[nmax];

int n,i,stiv1_size,stiv2_size;

bool cmpy (punct A , punct B)
{
    if (A.x!=B.x) return A.x<B.x;
    return A.y<B.y;
}

double cross_product (punct O,punct A,punct B) /// O este punctul noua origine
{
    A.x-=O.x;
    A.y-=O.y;
    B.x-=O.x;
    B.y-=O.y;
    return A.x*B.y-A.y*B.x;
}

int main()
{
    f>>n;
    for (i=1;i<=n;i++)
     f>>a[i].x>>a[i].y;

    sort(a+1,a+n+1,cmpy);

    stiv1_size=2;
    stiv1[1]=a[1];
    stiv1[2]=a[2];

    for (i=3;i<=n;i++) // partea dreapta
    {
        while (stiv1_size>=2 && cross_product(stiv1[stiv1_size-1],stiv1[stiv1_size],a[i])<0)
            stiv1_size--;

        stiv1[++stiv1_size]=a[i];
    }

    stiv2_size=2;
    stiv2[1]=a[n];
    stiv2[2]=a[n-1];

    for (i=n-2;i>=1;i--)
    {
        while (stiv2_size>=2 && cross_product(stiv2[stiv2_size-1],stiv2[stiv2_size],a[i])<0)
            stiv2_size--;

        stiv2[++stiv2_size]=a[i];
    }

    g<<setprecision(6)<<fixed;

    g<<stiv1_size+stiv2_size-2<<'\n';
    for (i=1;i<=stiv1_size;i++)
      g<<stiv1[i].x<<" "<<stiv1[i].y<<'\n';
    for (i=2;i<stiv2_size;i++)
     g<<stiv2[i].x<<" "<<stiv2[i].y<<'\n';
    return 0;
}