Cod sursa(job #2753926)

Utilizator cyg_mihaizMIHAI ZARAFIU cyg_mihaiz Data 24 mai 2021 18:54:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>

using namespace std;
const int NMAX = 120000;
const double eps = 1.0e-14;
const double INF = 1e9;

struct POINT
{
    double x, y;
};

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

POINT ll;
POINT v[NMAX + 5];

int h[NMAX + 5];

double cp(POINT P1, POINT P2, POINT P3)
{
    return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(POINT P1, POINT P2, POINT P3)
{
    double k = cp(P1, P2, P3);
    if(fabs(k) < eps)
        return 0;
    if(k >= eps)
        return 1;
    return -1;
}
bool cmp(POINT P1, POINT P2)
{
    return ccw(ll, P1, P2) > 0  ;
}
int main()
{
    int n, i;
    cin >> n;
    cin >> v[0].x >> v[0].y;
    for(i = 1; i < n; i++){
        cin >> v[i].x >> v[i].y;
        if(v[i].y - v[0].y <= -eps or (fabs(v[i].y - v[0].y) < eps and v[i].x - v[0].x <= -eps))
            swap(v[0], v[i]);
    }
    ll = v[0];
    sort(v + 1, v + n, cmp);
    h[0] = 0;
    h[1] = 1;
    v[n] = v[0];
    int top = 1;
    i = 2;
    while(i <= n){
        if(ccw(v[h[top - 1]], v[h[top]], v[i]) > 0){
            h[++top] = i;
            i++;
        }
        else
            top--;
    }
    cout << top << "\n";
    for(i = 0; i < top; i++)
        cout << fixed << setprecision(6) << v[h[i]].x << " " << v[h[i]].y << "\n";
    cout << "\n";
    return 0;
}