Cod sursa(job #2515409)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 28 decembrie 2019 15:38:55
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.6 kb
#include <bits/stdc++.h>
#define NM 120005
#define EPS 1e-9
using namespace std;
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;
    }


} v[NM], minn, maxx;
long double cross(point A, point B)
{
    return A.x*B.y - A.y*B.x;
}
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)
{
    point O = {0, 0};
    if(cross(B-O, B-A) < 0)
        return 0;
    return 1;
}
int n;
vector<point> sol1, sol2;
ifstream fin ("infasuratoare.in");
int main()
{
    FILE *fout;
    fout = fopen( "infasuratoare.out", "w" );
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;
    sort(v+1, v+1+n, cmp);
    minn = v[1], maxx = v[n];
    for(int i=1; i<=n; i++)
    {
        if(cross(minn-v[i], maxx-v[i]) >= 0)
        {
            if(sol1.size() > 1)
            {
                point C = sol1[sol1.size()-1] - sol1[sol1.size()-2];
                point D = v[i] - sol1[sol1.size()-1];
                while(cross(C, D) > 0 && sol1.size() > 1)
                {
                    sol1.pop_back();
                    C = sol1[sol1.size()-1] - sol1[sol1.size()-2];
                    D = v[i]-sol1[sol1.size()-1];
                }
            }
            sol1.push_back(v[i]);
        }
        else
        {
            if(sol2.size() > 1)
            {
                point C = sol2[sol2.size()-1] - sol2[sol2.size()-2];
                point D = v[i] - sol2[sol2.size()-1];
                while(cross(C, D) < 0 && sol2.size() > 1)
                {
                    sol2.pop_back();
                    C = sol2[sol2.size()-1] - sol2[sol2.size()-2];
                    D = v[i] - sol2[sol2.size()-1];
                }
            }
            sol2.push_back(v[i]);
        }
    }
    for(auto it:sol2)
        sol1.push_back(it);
    fprintf(fout, "%d\n", sol1.size());
    sort(sol1.begin(), sol1.end(), cmp2);
    for(int i=0; i<sol1.size(); i++)
    {
        fprintf(fout,"%.12Lf", sol1[i].x);
        fprintf(fout, " ");
        fprintf(fout,"%.12Lf\n", sol1[i].y);

    }
    fclose( fout );


    return 0;
}