Cod sursa(job #3300731)

Utilizator David-OvidiuDavid Ovidiu David-Ovidiu Data 18 iunie 2025 18:10:31
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.52 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <limits>

using namespace std;

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

double angle( double x1, double x2, double y1, double y2 )
{
    if ( x2 == x1 )
    {
        if ( y2 > y1 )
            return numeric_limits<double>::infinity();
        else 
            return (-1)*numeric_limits<double>::infinity();
    }
    return (y2-y1)/(x2-x1);
}

int lessthan180 ( double x1, double x2, double x3, double y1, double y2, double y3 )
{   
    if ( x3 == x1 && x2 < x1 )
        return 0;
    if ( x3 > x1 && angle(x1,x3,y1,y3) < 0)
    {
        if ( (x2 - x1)*angle(x1,x3,y1,y3) - (y2-y1) < 0 ) 
            return 0;
        return 1;
    }
    if ( x3 < x1 && angle(x1,x3,y1,y3) < 0)
    {
        if ( (x2 - x1)*angle(x1,x3,y1,y3) - (y2-y1) > 0 ) 
            return 0;
        return 1;
    }
    if ( x3 > x1 && angle(x1,x3,y1,y3) > 0)
    {
        if ( (x2 - x1)*angle(x1,x3,y1,y3) - (y2-y1) < 0 ) 
            return 0;
        return 1;
    }
    if ( x3 < x1 && angle(x1,x3,y1,y3) > 0)
    {
        if ( (x2 - x1)*angle(x1,x3,y1,y3) - (y2-y1) > 0 ) 
            return 0;
        return 1;
    }
    return 1;
}
void quicksort( double *x, double *y, int st, int dr, double x_min, double y_min)
{
	if(st < dr)
	{
		int m = (st + dr) / 2;
		double aux = x[st];
		x[st] = x[m];
		x[m] = aux;

        aux = y[st];
		y[st] = y[m];
		y[m] = aux;
		int i = st , j = dr, d = 0;
		while(i < j)
		{
			if(angle(x_min,x[i],y_min,y[i]) > angle(x_min,x[j],y_min,y[j]))
			{
				aux = x[i]; 
				x[i] = x[j];
				x[j] = aux;

                aux = y[i]; 
				y[i] = y[j];
				y[j] = aux;

				d = 1 - d;
			}
			i += d;
			j -= 1 - d;
		}
		quicksort(x,y, st , i - 1,x_min,y_min);
		quicksort(x,y, i + 1 , dr,x_min,y_min);
	}
}

int main(void)
{
    int n;
    double x[120001],y[120001];
    double x_min=0, y_min,y_start=0,x_start;
    fin >> n;
    for ( int i = 0 ; i < n ; i++ )
    {
        fin >> x[i] >> y[i];
        if ( x[i] < x_min || i == 0 )
        {
            x_min = x[i];
            y_min = y[i];
        }
        if ( x[i] == x_min && y[i] < y_min )
        {
            y_min = y[i];
        }
        if ( y[i] < y_start || i == 0 )
        {
            y_start = y[i];
            x_start = x[i];
        }
        if ( y[i] == y_start && x[i] < x_start )
        {
            x_start = x[i];
        }
    }
    quicksort(x,y,0,n-1,x_min,y_min);
    int i = 2,top,prevtop;
    stack<int> st;
    st.push(0);
    st.push(1);
    do
    {
        top = st.top();
        st.pop();
        prevtop = st.top();
        st.push(top);
        while ( lessthan180(x[prevtop],x[top],x[i],y[prevtop],y[top],y[i]) != 1 )
        {
            cout << "Ok";
            st.pop();
            top = st.top();
            st.pop();
            prevtop = st.top();
            st.push(top);
        }
        st.push(i);
        i++;
    } while ( ( x[st.top()] != x[0] ) && i != n );

    stack<int> st1,st2;
    i = 0;
    while ( x[st.top()] != x_start || y[st.top()] != y_start )
    {
        i++;
        st1.push(st.top());
        st.pop();
    }
    st1.push(st.top());
    st.pop();
    i++;
    while ( st.empty() == 0 )
    {
        i++;
        st2.push(st.top());
        st.pop();
    }
    fout << i << endl;
    while ( st1.empty() == 0 )
    {
        fout << x[st1.top()] << " " << y[st1.top()] << endl;
        st1.pop();
    }
    while ( st2.empty() == 0 )
    {
        fout << x[st2.top()] << " " << y[st2.top()] << endl;
        st2.pop();
    }
    return 0;
}