Cod sursa(job #1533304)

Utilizator gigiduru123Gigi Duru gigiduru123 Data 22 noiembrie 2015 13:13:38
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct point
{
    double x, y;
    bool operator < (const point &p) const
    {
        return x<p.x or (x==p.x and y<p.y);
    }
};
int n;
vector <point> V, H;
double det (point A, point B, point C)
{
    return (double)(B.x-A.x)*(C.y-A.y)-(double)(B.y-A.y)*(C.x-A.x);
}

int main()
{
    point p;
    in >> n;
    for (int i = 0; i < n; ++i)
    {   in >> p.x >> p.y;
        V.push_back(p);
    }
    sort(V.begin(), V.end());
    H.resize(2*n);
    int k = 0;
    for (int i = 0; i < n; ++i)
    {
        while(k >= 2 and det(H[k-2], H[k-1], V[i]) <= 0) --k;
        H[k++] = V[i];
    }
    for (int i = n - 2, t = k + 1; i; --i)
    {   while (k >= t and det(H[k-2], H[k-1], V[i]) <= 0) --k;
        H[k++] = V[i];
    }
    H.resize(k);
    out << H.size() - 1 << '\n';
    for (int i = 0; i < H.size() - 1; ++i) out << fixed << setprecision(6) << H[i].x << ' ' << H[i].y << '\n';
    out.close();
    return 0;
}