Cod sursa(job #3273299)

Utilizator BucsMateMate Bucs BucsMate Data 1 februarie 2025 15:51:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <float.h>
#include <iomanip>

using namespace std;

const double INF = DBL_MAX;

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

struct Pont
{
    double x;
    double y;
    double slope;
};



double slope(Pont start, Pont veg)
{
    if(veg.y - start.y == 0){
        return INF;
    }
    return -(veg.x-start.x)/(veg.y-start.y);
}

bool comp(Pont p1, Pont p2)
{
    return (p1.slope < p2.slope);
}

double crossProduct(Pont p1, Pont p2, Pont p3)
{
    return (p2.x*p3.y + p1.x*p2.y + p3.x*p1.y - p2.x*p1.y - p3.x*p2.y - p1.x*p3.y);
}

/*
|1  1  1 |
|x1 x2 x3|= x1y2 + x2y3 + x3y1 - x3y2 - x2y1 - x1y3
|y1 y2 y3|


*/

int main()
{
    int N;
    fin >> N;
    vector<Pont> pontok(N);
    int startPont = 0;
    Pont start;
    for(int i = 0; i < N; i++){
        fin >> pontok[i].x >> pontok[i].y;
        if(pontok[startPont].y > pontok[i].y){
            startPont = i;
        }
        else if(pontok[startPont].y == pontok[i].y && pontok[startPont].x > pontok[i].x){
            startPont = i;
        }
    }
    for(int i = 0; i < N; i++){
        pontok[i].slope = slope(pontok[startPont], pontok[i]);
    }
    /*for(int i = 0; i < N; i++){
        cout << slope(pontok[startPont], pontok[i]) << endl;
    }*/
    start = pontok[startPont];
    //cout << pontok[startPont].x << " " << pontok[startPont].y << endl;
    //cout << start.x << " " << start.y << endl << endl;
    sort(pontok.begin(), pontok.end(), comp);

    for(int i = 0; i < N; i++){
        if(pontok[i].x == start.x && pontok[i].y == start.y){
            startPont = i;
            break;
        }
    }

    int secondToLast;
    stack<int> st;
    st.push(startPont);
    st.push(0);
    for(int i = 1; i < N; i++){
        if(i == startPont){
            continue;
        }
        int temp = st.top();
        st.pop();
        secondToLast = st.top();
        st.push(temp);
        while(crossProduct(pontok[secondToLast], pontok[st.top()], pontok[i]) <= 0 && st.size() >= 2){
            st.pop();
            if(st.size() < 2){
                break;
            }
            temp = st.top();
            st.pop();
            secondToLast = st.top();
            st.push(temp);
        }
        st.push(i);
    }
    stack<int> result;
    while(!st.empty()){
        result.push(st.top());
        st.pop();
    }
    fout << result.size() << endl;
    while(!result.empty()){
        fout << fixed << setprecision(6) << pontok[result.top()].x << " " << pontok[result.top()].y << endl;
        result.pop();
    }

    return 0;
}