Cod sursa(job #2515485)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 28 decembrie 2019 18:03:03
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
#define NM 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const long double EPS = 1e-12;
struct point
{
    long double x, y;
        point() {}
    point(long double x, long double y): x(x), y(y) {}
    point& operator+=(const point &t) {
        x += t.x;
        y += t.y;
        return *this;
    }
    point& operator-=(const point &t) {
        x -= t.x;
        y -= t.y;
        return *this;
    }
    point operator+(const point &t) const {
        return point(*this) += t;
    }
    point operator-(const point &t) const {
        return point(*this) -= t;
    }

};
point v[NM];
point O = {0, 0};
int n, s1[NM], s2[NM], h1, h2;
long double cross(point A, point B)
{
    return A.x*B.y - A.y*B.x;
}
bool turns_left(point A, point B, point C)
{
    if(cross(B-A, C-B) > EPS)
        return 1;
    return 0;
}
bool cmp(point A, point B)
{
    return A.x < B.x || (A.x == B.x && A.y < B.y);
}
bool cmp2(point A, point B)
{
    if(turns_left(O, A, B) > EPS)
        return 1;
    return 0;
}
int main()
{
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;
    sort(v+1, v+1+n, cmp);
    point first = v[1], last = v[n];
    s1[++h1] = 1;
    for(int i=2; i<n; i++)
        if(turns_left(first, last, v[i]))
        {
            while(h1>=2 && turns_left(v[s1[h1-1]], v[s1[h1]], v[i]))
                h1--;
            s1[++h1] = i;
        }
        else
        {
            while(h2>=2 && !turns_left(v[s2[h2-1]], v[s2[h2]], v[i]))
                h2--;
            s2[++h2] = i;
        }
    s1[++h1] = n;
    vector<point> sol;
    for(int i=1; i<=h1; i++)
        sol.push_back(v[s1[i]]);
    for(int i=1; i<=h2; i++)
        sol.push_back(v[s2[i]]);
    sort(sol.begin(), sol.end(), cmp2);
    fout << sol.size() << '\n';
    fout << setprecision(12) << fixed;
    for(auto it:sol)
        fout << it.x << ' ' << it.y << '\n';

    return 0;
}