Cod sursa(job #3226990)

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

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
    double x, y;

}a[103005];

int n;
double getWay(Point A, Point B, Point C)
{

    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);

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

void Citire()
{
    fin >> n;
    for(int i = 1;i <= n;i++)
        fin >> 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[130005];
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;
    }
    fout << top << "\n";
    while(top){
        fout << setprecision(9) << fixed << a[stv[top]].x << " " << a[stv[top]].y << "\n";
        top--;
    }

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