Cod sursa(job #2496649)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 21 noiembrie 2019 12:21:33
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define NMAX 120005

using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

int n;

struct Point
{
    long double x , y;
}a[NMAX];

Point s[NMAX];

long long Aria(Point a , Point b , Point c)
{
    Point dif = {c.x - a.x , c.y - a.y};
    a = {0 + dif.x , 0 + dif.y};

    dif = {c.x - b.x , c.y - b.y};
    b = {0 + dif.x , 0 + dif.y};

    return a.x * b.y - b.x * a.y;
}


bool inline Custom_Compare(Point c , Point b)
{
    return Aria(c , b , a[1]) < 0;
}

int main()
{
    int i , top;

    f >> n;

    for(i = 1 ; i <= n ; i++)
    {
        f >> a[i].x >> a[i].y;

        if(a[1].x > a[i].x)
            swap(a[1] , a[i]);
        else if(a[1].x == a[i].x)
            if(a[1].y > a[i].y)
                swap(a[1] , a[i]);
    }

    sort(a + 2 , a + n + 1, Custom_Compare);

    s[1] = a[1];
    s[2] = a[2];
    top = 2;

    for(i = 3 ; i <= n ; i++)
    {
        while(top >= 2 && Aria(s[top] , a[i] , s[top - 1]) > 0)
            --top;

        s[++top] = a[i];
    }

    g << top << '\n';

    for(i = top ; i >= 1 ; i--)
        g << fixed << setprecision(6) << s[i].x << ' ' << s[i].y << '\n';

    return 0;
}