Cod sursa(job #2959287)

Utilizator maiaauUngureanu Maia maiaau Data 30 decembrie 2022 15:32:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int N = 12e4 + 5;

struct pt{
    double x, y;
} v[N];

int n, s[N], k;

void prep(), solve();
inline void read(), prt();
bool sortTrig(pt, pt);
inline double det(pt, pt, pt), dist(pt, pt);

int main()
{
    prep();
    solve();
    prt();
    return 0;
}
inline void read(){
    f >> n;
    for (int i = 0; i < n; i++)
        f >> v[i].x >> v[i].y;
}
bool sortTrig(pt a, pt b){
    return (det(v[0], a, b) > 0 ? true : false);
}
inline double det(pt a, pt b, pt c){
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
void prep(){
    read();
    for (int i = 1; i < n; i++)
        if (v[i].y > v[0].y || (v[i].y == v[0].y && v[i].x > v[i].y))
            swap(v[0], v[i]);
    sort(v + 1, v + n, sortTrig);
}
void solve(){
    s[0] = 0; s[++k] = 1;
    for (int i = 2; i < n; i++){
        while (k >= 1 && det(v[s[k - 1]], v[s[k]], v[i]) <= 0) k--;
        s[++k] = i;
    }
}
inline void prt(){
    g << k + 1 << '\n';
    for (int i = 0; i <= k; i++) g << fixed << setprecision(12) << v[s[i]].x << ' ' << v[s[i]].y << '\n';
}