Cod sursa(job #1509846)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 24 octombrie 2015 12:44:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
#define eps 1e-12
/// eps este 10^(-12) , se foloseste pentru diferente foarte mici , de exemplu 1.00000006 si 1.00000003
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 de jos (pentru ca le-am ordonat dupa x , vom veni din stnanga jos)
    {
        while (stiv1_size>=2 && cross_product(stiv1[stiv1_size-1],stiv1[stiv1_size],a[i])<eps) /// cand cross-productul este mai mic decat 0 (sau epsilon) , inseamna ca punctul actual scoate punctul de dinainte
            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--) /// partea de sus
    {
        while (stiv2_size>=2 && cross_product(stiv2[stiv2_size-1],stiv2[stiv2_size],a[i])<eps)
            stiv2_size--;

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

    g<<setprecision(6)<<fixed; /// fixam precizia zecimalelor la 6

    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;
}