Cod sursa(job #3226985)

Utilizator NeganAlex Mihalcea Negan Data 23 aprilie 2024 19:56:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

struct Point{
    double x, y;

}a[100005];

int n;
double getWay(Point A, Point B, Point C)
{
    double xAB, yAC, xAC, yAB;
    xAB = B.x - A.x;
    yAB = B.y - A.y;
    xAC = C.x - A.x;
    yAC = C.y - A.y;
    return 1LL * xAB * yAC - 1LL * yAB * xAC;

}
bool cmp(Point A, Point B)
{
    return getWay(a[0], A, B) < 0;
}

void Citire()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i].x >> a[i].y;
    int minP = -1;
    double minim = 1e9;
    for(int i = 1;i <= n;i++)
        if(minim > a[i].y){
            minim = a[i].y;
            minP = i;
        }
    swap(a[1], a[minP]);
    sort(a + 1, a + n + 1, cmp);

}
int stv[100005];
void ConvexHull()
{
    int top = 0;
    stv[++top] = 1;
    stv[++top] = 2;
    for(int i = 3;i <= n;i++){
        while(top >= 2 && getWay(a[stv[top - 1]], a[stv[top]], a[i]) >= 0)
            top--;
        stv[++top] = i;
    }
    cout << top << "\n";
    while(top){
        cout << setprecision(9) << fixed << a[stv[top]].x << " " << a[stv[top]].y << "\n";
        top--;
    }

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