Cod sursa(job #2049281)

Utilizator FredyLup Lucia Fredy Data 27 octombrie 2017 00:01:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

#define lim 120010
struct point {double x, y;} ini[lim], stiva[lim];
int n,minm;

double det(point a, point b, point c)
{
    return a.x*b.y + b.x*c.y + a.y*c.x - c.x*b.y - b.x*a.y - c.y*a.x;
}

bool cmp (point A, point B)
{
    return det (ini[1],A,B) >=0;
}

int main()
{
    fin>>n;
    minm=1;
    for (int i=1; i<=n; i++)
    {
        fin>>ini[i].x>>ini[i].y;
        if (ini[i].x > ini[minm].x) minm=i;
        else if (ini[i].x==ini[minm].x && ini[i].y<ini[minm].y)    minm=i;
    }
    swap (ini[1], ini[minm]);
    sort (ini+2, ini+n+1, cmp);

    int dr=0;
    for (int i=1; i<=n; i++)
    {
        while (dr>1 &&  det (stiva[dr-1],stiva[dr],ini[i]) < 0) dr--;
        dr++;
        stiva[dr]=ini[i];
    }

    fout<<dr<<'\n';
    for (int i=1; i<=dr; i++)
        fout<<fixed<<stiva[i].x<<' '<<stiva[i].y<<'\n';

    fin.close();
    fout.close();
    return 0;
}