Cod sursa(job #2910374)

Utilizator proflaurianPanaete Adrian proflaurian Data 20 iunie 2022 11:18:47
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double,double> punct;
const int N = 120002;
int n;
punct P[N],O;
vector<punct> H;///infasuratoarea


punct vect(punct A)
{
    return make_pair(A.X-O.X,A.Y-O.Y);
}

double lung(punct A)
{
    return sqrt(A.X*A.X+A.Y*A.Y);
}
double dist(punct A,punct B)
{
    return sqrt((B.X-A.X)*(B.X-A.X)+(B.Y-A.Y)*(B.Y-A.Y));;
}
double unghi(punct A)
{
    return atan2(A.Y,A.X);
}
bool crit(punct A,punct B)
{
    A=vect(A);
    B=vect(B);
    double alfa=unghi(A);
    double beta=unghi(B);
    if(alfa<beta)return true;
    if(beta<alfa)return false;
    return lung(A)<lung(B);
}
bool elimin(punct A,punct B,punct C)
{
    /// sunt in punctul A si privesc spre B
    /// daca vad punctul in dreapta trebuie sa elimin
    /// daca vad punctul in stanga nu trebuie sa elimin
    /// daca punctele sunt coliniare
        /// daca B este mai aproape de A elimin
        /// daca B este mai departe de A pastrez
    double delta=A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X;
    if(delta<0)return true;
    if(delta>0)return false;
    if(dist(A,B)<dist(A,C));return true;
    return false;
}
int main()
{
    f>>n;
    for(int i=0; i<n; i++)
    {
        double x,y;
        f>>x>>y;
        P[i]=make_pair(x,y);
    }

    /// se alege cel mai "mic" punct

    int j=0;
    for(int i=1; i<n; i++)
        if(P[i]<P[j])
            j=i;

    /// se pune punctul pe pozitia 0

    swap(P[0],P[j]);
    O=P[0];

    /// se ordoneaza punctele dupa unghi luand drept reper P[0]

    sort(P+1,P+n,crit);
    /// punem in stiva primele doua puncte
    H.push_back(P[0]);
    H.push_back(P[1]);
    int m=1;
    /// consideram urmatoarele puncte
    /// scoatem din stiva
    for(int i=2;i<n;i++)
    {
        /// cat timp am doua puncte in stiva
        /// si urmatorul punct se vede spre dreapta
        /// se scoate ultimul punct din stiva
        while(m>0 && elimin(H[m-1],H[m],P[i]))
        {
            H.pop_back();m--;
        }
        H.push_back(P[i]);m++;
    }
    g<<H.size()<<'\n';
    for(auto p:H)
        g<<fixed<<setprecision(12)<<p.X<<' '<<p.Y<<'\n';
    return 0;
}