Cod sursa(job #2574720)

Utilizator victorzarzuZarzu Victor victorzarzu Data 6 martie 2020 09:16:48
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
Raporteaza aceasta sursa 
#include <bits/stdc++.h>
using namespace std;

struct Point{
    double x, y;
};

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
Point v[120005];
double sumx, sumy, x, y;
int head = 1;
Point s[120005];

double cross_product(Point A, Point B, Point C)
{
    return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x);
}

bool cmp(Point A, Point B)
{
    return cross_product(v[0], A, B) < 0;
}

void Read()
{
    f>>n;
    for(int i = 0;i < n;++i)
    {
        f>>v[i].x>>v[i].y;
        sumx += x;
        sumy += y;
    }

    int pos = 0;
    for(int i = 1;i < n;++i)
    {
        if(v[i].x < v[pos].x)
            pos = i;
        else if(v[i].x == v[pos].x && v[i].y < v[pos].y)
            pos = i;
    }
    swap(v[0], v[pos]);
    sort(v + 1, v + n, cmp);
}

void convex_hull()
{
    s[0] = v[0];
    s[1] = v[1];
    for(int i = 2;i < n;++i)
    {
        while(head >= 2 && cross_product(s[head - 1], s[head], v[i]) > 0)
            --head;
        s[++head] = v[i];
    }
}

void Print()
{
    g<<setprecision(12)<<fixed;
    g<<head + 1<<'\n';
    for(int i = head;i >= 0;--i)
        g<<s[i].x<<" "<<s[i].y<<'\n';
}

int main()
{
    Read();
    convex_hull();
    Print();
    return 0;
}