Cod sursa(job #2286236)

Utilizator BurlacuMateiBurlacu Matei BurlacuMatei Data 19 noiembrie 2018 22:50:24
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define MAX 120100
#define INT_MAX 2000000000

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct{
    double x;
    double y;
}p[MAX], stiva[MAX], minim;
int pozm;

int n, vf;
bool m(punct x)
{
    if(x.x < minim.x) return 1;
    else if(x.x == minim.x)
            if(x.y < minim.y) return 1;

    return 0;
}

bool cmp(punct p1, punct p2){
int prod;

    prod = p1.x * p2.y - p2.x * p1.y;
    if(prod > 0) return 1;
    else if(prod < 0) return 0;
    else if(p1.x < p2.x) return 1;
    else return 0;
}
bool cmp2(punct p1, punct p2, punct p3){
int prod;

    p2.x -= p1.x; p2.y -= p1.y;
    p3.x -= p1.x; p3.y -= p1.y;
    prod = p2.x * p3.y - p3.x * p2.y;
    if(prod > 0) return 1;
    else if(prod < 0) return 0;
    else if(p1.x < p2.x) return 1;
    else return 0;
}
int main()
{int i;

    minim.x = INT_MAX;
    minim.y = INT_MAX;
    fin >> n;
    for(i = 1;i <= n; i++)
    {
        fin >> p[i].x;
        fin >> p[i].y;

        if(m(p[i]))
            {
                minim = p[i];
                pozm = i;
            }
    }

    swap(p[0], p[pozm]);
    swap(p[pozm], p[n]);

    for(i = 0;i < n; i++)
    {
        p[i].x -= minim.x;
        p[i].y -= minim.y;
    }
    sort(p + 1, p + n, cmp);

    stiva[1] = p[0];
    stiva[2] = p[1];
    vf = 2;

    for(i = 2;i < n; i++)
    {
        if(cmp2(stiva[vf - 1], stiva[vf], p[i]))
        {
            vf++;
            stiva[vf] = p[i];
        }
        else
        {
            vf--;
            for(; vf >= 2; vf--)
            {
                if(cmp2(stiva[vf - 1], stiva[vf], p[i]))
                    {
                        vf++;
                        stiva[vf] = p[i];
                        break;
                    }
            }
        }

    }

    fout << vf << '\n';
    //fout << fixed << setprecision(6) << stiva[1].x + minim.x << ' ' << stiva[1].y + minim.y <<'\n';
    for(i=1;i<=vf;i++)
        fout<< fixed << setprecision(6) << stiva[i].x + minim.x <<' '<<stiva[i].y + minim.y <<'\n';
    return 0;
}