Cod sursa(job #2154545)

Utilizator AndreiDumitrescuAndrei Dumitrescu AndreiDumitrescu Data 7 martie 2018 03:28:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <algorithm>
#define maxN 120005

using namespace std;

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

typedef struct{
    double x;
    double y;
}point;

point v[maxN], stiva[maxN];
int n, h;

double det(point a, point b, point c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y);
}

double dist(point a, point b)
{
    double dist;
    dist = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    return dist;
}

int comparare(point a, point b)
{
    if(a.x == b.x && a.y == b.y)
        return 0;
    return 1;
}

bool compare_determinant(const point a, const point b)
{
    if(det(a,b, v[1]) > 0)
    {
        return true;
    }
    if(det(a,b, v[1]) < 0)
    {
        return false;
    }
    if(det(a,b, v[1]) == 0)
    {
        return ((dist(v[1], a) < dist(v[1],b)));
    }
}


int extrem()
{
    point rez;
    rez.x = 0;
    rez.y = 0;
    double minim = 9999999999;
    int poz;
    for(int i = 1; i <= n; i++)
    {
        if(v[i].x == minim)
        {
            if(v[i].y < rez.y)
            {
                rez.x = v[i].x;
                rez.y = v[i].y;
                poz = i;
            }
        }
        if(v[i].x < minim)
        {
            minim = v[i].x;
            rez.x = v[i].x;
            rez.y = v[i].y;
            poz = i;
        }
    }
    return poz;
}

int main()
{
    f >> n;
    point aux;
    int poz, k = 0, i;
    for(i = 1; i <= n; i++)
    {
        f >> v[i].x >> v[i].y;
    }
    poz = extrem();
    if(poz != 1)
    {
        aux.x = v[1].x;
        aux.y = v[1].y;
        v[1].x = v[poz].x;
        v[1].y = v[poz].y;
        v[poz].x = aux.x;
        v[poz].y = aux.y;
    }
    sort(v+2, v+n+1, compare_determinant);
    for(i = 1; i <= n ;i++)
    {
        while(k >= 2)
        {
            k--;
            if(det(stiva[k], stiva[k+1],v[i]) <= 0)
                continue;
            k++;
            break;
        }
        k++;
        stiva[k].x = v[i].x;
        stiva[k].y = v[i].y;
    }
    g << k << '\n';
    for(i = 1 ; i <= k; i++)
    {
        g << setprecision(12) << fixed <<stiva[i].x << " " << stiva[i].y << '\n';
    }

}