Cod sursa(job #1594903)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 9 februarie 2016 20:04:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cstdio>
#include <iomanip>
using namespace std;
#define mp make_pair
#define x first
#define y second
#define eps 0.000001
#define inf 1 << 31
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i,j,n,m,k;
pair<double,double> v[120005],rasp[120005];
bool ok(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
    return(a.x * b.y + b.x * c.y + c.x * a.y - ( b.y * c.x + c.y * a.x + a.y * b.x ) ) <= 0;
}
int main()
{
    fin >> n;
    sort(v+1, v+1+n);
    for(i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
    for(i = 1; i <= n; i++)
    {
        while(j > 1 && ok(rasp[j - 1], rasp[j], v[i]))
            j--;
        j++;
        rasp[j] = v[i];
    }
    k = j;
    for(i = n - 1; i > 0; i--)
    {
        while(j > k  && ok(rasp[j - 1], rasp[j], v[i]))
            j--;
        j++;
        rasp[j] = v[i];
    }
    j--;
    fout << setprecision(6) << fixed;
    fout << j << '\n';
    for(i = 1; i <= j; i++)
        fout << rasp[i].x<<" "<<rasp[i].y<<'\n';
    return 0;
}