Cod sursa(job #2756375)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 31 mai 2021 11:44:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
using ld = long double;
const ld eps = 1.e-12;
class Point {
public:
    ld x, y;
    Point() : x(0), y(0) {}
    Point(ld _x, ld _y) : x(_x), y(_y) {}
    Point operator +(const Point& other) {return Point(x + other.x, y + other.y);}
    Point operator -(const Point& other) {return Point(x - other.x, y - other.y);}
    friend ld cp(const Point& a, const Point& b) {return a.x * b.y - a.y * b.x;}
    friend int ccw(Point a, Point b, Point c) {ld cross = cp(b - a, c - a); if(abs(cross) < eps) return 0; if(cross >= eps) return 1; return -1;}
    friend istream& operator >>(istream& in, Point& v) {return in >> v.x >> v.y;}
    friend ostream& operator <<(ostream& out, const Point& v) {return out << v.x << " " << v.y;}
};
const int NMAX = 12e4;
Point LL, P[NMAX + 5];
int h[NMAX + 5];

int main()
{
    int n, top;
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> P[i];
    for_each(P + 1, P + n, [&](Point& p){if(abs(p.y - P[0].y) < eps && p.x - P[0].x <= -eps) swap(P[0], p); else if(p.y - P[0].y <= -eps) swap(P[0], p);});
    P[n] = LL = P[0];
    sort(P + 1, P + n, [](const Point& a, const Point& b){return (ccw(LL, a, b) > 0);});
    h[0] = 0, h[1] = 1, top = 1; int i = 2;
    while(i <= n)
        if(ccw(P[h[top - 1]], P[h[top]], P[i]) > 0)
            h[++top] = i++;
        else top--;
    fout << top << "\n" << fixed << setprecision(6);
    for(int i = 0; i < top; i++)
        fout << P[h[i]] << "\n";
    return 0;
}