Cod sursa(job #2209515)

Utilizator DordeDorde Matei Dorde Data 3 iunie 2018 18:25:14
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 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)
{
    int i , j;
    double m [7][7];
    m [1][1] = a . x;
    m [1][2] = a . y;
    m [2][1] = b . x;
    m [2][2] = b . y;
    m [3][1] = p . x;
    m [3][2] = p . y;
    for(i = 1 ; i <= 3; ++ i)
        m [i][3] = 1;
    copy (m [1] + 1 , m [1] + 4 , m [4] + 1);
    copy (m [2] + 1 , m [2] + 4 , m [5] + 1);
    ll y = 1 , ij = 0;
    for(i = 1 ; i <= 3 ; ++ i)
    {
        y = 1;
        for(j = 1 ; j <= 3 ; ++ j)
            y = y * (m [i + j - 1][j]);
        ij = ij + y;
    }
    for(i = 3 ; i >= 1 ; -- i)
    {
        y = 1;
        for(j = 3 ; j >= 1 ; -- j)
            y = y * (m [3 - j + 1 + 3 - i][j]);
        ij = ij - y;
    }
    return ij;

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