Cod sursa(job #2209521)

Utilizator DordeDorde Matei Dorde Data 3 iunie 2018 18:30:06
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
int const NM = 12e4 + 7;
int n;
int vl [NM] , vr [NM];
typedef long long ll;
struct code
{
    double x , y;
    int type;
    /// 1 stanga
    /// -1 dreapta
    /// 0 centru
};
code v [NM];
inline bool crt (code a , code b)
{
    if(a . x == b . x)
        return a . y < b . y;
    return a . x < b . x;
}
inline int where (code a , code b , code p)
{
    return ((a.x*b.y+b.x*p.y+p.x*a.y)-(b.y*p.x+p.y*a.x+a.y*b.x));
}
int szl , szr;
inline void left ()
{
    int i;
    vl [++ szl] = 1;
    for(i = 2 ; i <= n ; ++ i)
    {
        while( szl > 1 && where (v [vl [szl - 1]] , v [vl [szl]] , v [i]) > 0)
            -- szl;
        vl [++ szl] = i;
    }
    return;
}
inline void right ()
{
    int i = 2;
    vr [++ szr] = 1;
    for(i = 2 ; i <= n ; ++ i)
    {
        while(szr > 1 && where (v [vr [szr - 1]] , v [vr [szr]] , v [i]) < 0)
            -- szr;
        vr [++ szr] = i;
    }
    return ;
}
char const in [] = "infasuratoare.in";
char const out [] = "infasuratoare.out";
ofstream cout (out);
int main ()
{
    int i;
    FILE *cin ;
    cin = fopen (in , "r");
    fscanf (cin , "%d" , &n);
    for(i = 1 ; i <= n ; ++ i)
        fscanf (cin , "%lf %lf" , &v [i] . x , &v [i] . y);
    sort (v + 1 , v + n + 1 , crt);
    code start = v [1] , finish = v [n];
    for(i = 2 ; i < n ; ++ i)
        v [i] . type = where (start , finish , v [i]);
    left ();
    right ();
    cout << szl + szr - 2 << '\n';
    for(i = 1 ; i <= szr ; ++ i)
        cout << fixed << setprecision(12) << v [vr [i]] . x << ' ' << v [vr [i]] . y << '\n';
  //  cout << '\n';
    for(i = szl - 1 ; i > 1 ; -- i)
        cout << fixed << setprecision(12) << v [vl [i]] . x << ' ' << v [vl [i]] . y << '\n';
    return 0;
}