Cod sursa(job #2067368)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 16 noiembrie 2017 12:01:03
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <deque>
#include <iomanip>
#include <vector>
#include <algorithm>
#define DIM 120002

using namespace std;

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

vector<int> sol;

int n, nr, viz[DIM];
double xmin, ymin;

deque<int> c;

struct punct{
    double x, y;
}pct[DIM];

double arie(punct a, punct b){
    return a.x * b.y - a.y * b.x;
}

double dist(punct a){
    return a.x * a.x + a.y * a.y;
}

bool cmp(punct a, punct b){
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

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

int main()
{
    f>>n;
    for(int i = 1; i <= n; ++ i){
        f>>pct[i].x>>pct[i].y;
        if(pct[i].x < xmin){
            xmin = pct[i].x;
        }
        if(pct[i].y < ymin){
            ymin = pct[i].y;
        }

    }
    for(int i = 1; i <= n; ++ i){
        pct[i].x += xmin;
        pct[i].y += ymin;
    }

    sort(pct + 1, pct + n + 1, cmp);

    c.push_back(1);
    c.push_back(2);
    //c.push_back(3);

    for(int i = 3; i <= n; ++ i){
        punct A, B, C;
        while(c.size() >= 2){
            A = pct[c[c.size() - 2]];
            B = pct[c[c.size() - 1]];
            C = pct[i];
            if(det(A, B, C) <= 0){
                c.pop_back();
            }
            else
                break;
        }
        c.push_back(i);
    }

    for(int i = 0; i < c.size(); ++ i)
        sol.push_back(c[i]);

    c.clear();

    c.push_back(n);
    c.push_back(n - 1);

    for(int i = n - 2; i >= 1; -- i){
        punct A, B, C;
        while(c.size() >= 2){
            A = pct[c[c.size() - 2]];
            B = pct[c[c.size() - 1]];
            C = pct[i];
            if(det(A, B, C) <= 0)
               c.pop_back();
            else
                break;
        }
        c.push_back(i);
    }

    for(int i = 1; i < c.size() - 1; ++ i)
        sol.push_back(c[i]);

    g<<sol.size()<<'\n';
    for(int i = 0; i < sol.size(); ++ i){
        g<<setprecision(10)<<fixed<<pct[sol[i]].x - xmin<<" ";
        g<<setprecision(10)<<fixed<<pct[sol[i]].y - ymin<<'\n';
    }

    return 0;

}