Cod sursa(job #1816232)

Utilizator horiainfoTurcuman Horia horiainfo Data 26 noiembrie 2016 11:45:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iomanip>

#define INF 1000000002
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Point{double x, y;};
int n;
Point p[120002];
vector<Point> co;

double sign(Point p1, Point p2, Point p3)
{
    return (p1.x * p2.y + p1.y * p3.x + p2.x * p3.y) - (p2.y * p3.x + p2.x * p1.y + p1.x * p3.y);
}

bool test(Point p1, Point p2)
{
    return sign(p[0], p1, p2) < 0;
}

int main()
{
    fin >> n;

    int maxX = -INF;
    int pos = 0;
    for(int i = 0; i < n; i ++)
    {
        fin >> p[i].x >> p[i].y;
        if(p[i].x < p[pos].x || (p[i].x == p[pos].x && p[i].y < p[pos].y))
            pos = i;
    }

    swap(p[0], p[pos]);
    sort(p + 1, p + n, test);

    co.push_back(p[0]);
    for(int i = 1; i < n; i++)
    {
        while(co.size() > 1 && sign(co[co.size() - 2], co[co.size() - 1], p[i]) > 0)
            co.pop_back();
        co.push_back(p[i]);
    }

    fout << co.size() << '\n';
    fout << fixed << setprecision(6);
    for(int i = 0; i < co.size(); i ++)
        fout << co[i].x << ' ' << co[i].y << '\n';
    return 0;
}