Cod sursa(job #3203411)

Utilizator octavi26octavian octavi26 Data 13 februarie 2024 17:26:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>
#define N 120008

using namespace std;

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

int n, k;
struct point{
    double x, y;

    bool operator!=(point A){
        return A.x != x || A.y != y;
    }
    bool operator==(point A){
        return A.x == x && A.y == y;
    }
} v[N], sol[N];

void Citire()
{
    int i;
    fin >> n;
    for( i=1; i<=n; i++ ){
        fin >> v[i].x >> v[i].y;
    }
}

int Orientare( point A, point B, point C )
{
    if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) < 0 )
        return -1;
    if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) > 0 )
        return 1;
    return 0;
}

double dist( point A, point B ){
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

bool cmp( point A, point B )
{
    return Orientare( v[1], A, B ) > 0;
}

point st[N];
int top;

void Rezolvare()
{
    int i, p;
    point P;
    double ymn = 2e9;
    for( i=1; i<=n; i++ ){
        if( v[i].y < ymn ){
            ymn = v[i].y;
            P = v[i];
            p = i;
        }
        else if( v[i].y == ymn ) if( v[i].x < P.x ){
            P = v[i];
            p = i;
        }
    }
    swap( v[1], v[p] );
    sort( v + 2, v + n + 1, cmp );

    st[++top] = v[1];
    st[++top] = v[2];
    for( i=3; i<=n; i++ ){
        while( top >= 2 && Orientare( st[top - 1], st[top], v[i] ) <= 0 ) top--;
        st[++top] = v[i];
    }

    fout << top << "\n";
    fout << fixed << setprecision(12);
    for( i=1; i<=top; i++ ){
        fout << st[i].x << " " << st[i].y << "\n";
    }
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}