Cod sursa(job #2430297)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 13 iunie 2019 21:43:34
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>
#define NMAX 120005
#define inf 2147000000

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


int st[NMAX], P, N, k;
pair<double, double> M[NMAX];

class comp{
public:
    bool operator()(int a, int b){
        int y1, y2, x1, x2;
        y1 = M[a].second - M[P].second;
        y2 = M[b].second - M[P].second;
        x1 = M[a].first - M[P].first;
        x2 = M[b].first - M[P].first;
        return !(y1*x2 < y2*x1);
    }
};

priority_queue<int, vector<int>, comp> pq;

void read()
{
    double ymin = 1000000001, xmin = 1000000001;
    fin >> N;
    for(int i = 1; i <= N; i++){
        fin >> M[i].first >> M[i].second;
        if(M[i].first < xmin)
            xmin = M[i].first, ymin = M[i].second, P = i;
        else if(M[i].second == xmin && M[i].first < ymin)
            ymin = M[i].second, P = i;
    }
}

void SlopeSort()
{
    double x, y;
    for(int i = 1; i <= N; i++){
        if(i == P) continue;
        pq.push(i);
    }
}

bool convex(){
    int x1, x2, x3, y1, y2, y3;
    x1 = M[st[k - 2]].first, y1 = M[st[k - 2]].second;
    x2 = M[st[k - 1]].first, y2 = M[st[k - 1]].second;
    x3 = M[st[k - 0]].first, y3 = M[st[k - 0]].second;
    return (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1) > 0;
}

int main()
{
    read();

    SlopeSort();

    k = 2; st[1] = P; st[2] = pq.top(); pq.pop();

    while(!pq.empty()){
        st[++k] = pq.top(); pq.pop();
        while(!convex()){
            st[--k] = st[k + 1]; st[k + 1] = 0;
        }
    }

    fout << k << "\n";
    for(int i = 1; i <= k; i++) fout << M[st[i]].first << " " << M[st[i]].second << "\n";

    return 0;
}