Cod sursa(job #3204987)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 18 februarie 2024 15:10:55
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Radu{
    double x, y;
};
vector <Radu> v;
int n;
int cadran(int x, int y) {
    if( x > 0 && y >= 0 )
        return 1;
    if( x >= 0 && y < 0 )
        return 4;
    if( y > 0 && x <= 0 )
        return 2;
    return 3;
}

int det( double x1, double y1, double x2, double y2, double x3, double y3) {
    return x1 * (y2- y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
}

int cmp(const Radu &a, const Radu &b ) {
    int c1 = cadran(a.x, a.y);
    int c2 = cadran(b.x, b.y);
    if( c1 != c2 )
        return c1 < c2;
    int d = det( 0, 0, a.x, a.y, b.x, b.y);
    if( d != 0 )
        return d > 0;
    return a.x * a.x + a.y * a.y > b.x * b.x + b.y * b.y;
}
bool convex( Radu a, Radu b, Radu c ){
    return det( a.x, a.y, b.x, b.y, c.x, c.y ) > 0;
}
int main() {
    in >> n;
    for( int i = 0; i < n; i++ ){
        double a, b;
        in >> a >> b;
        v.push_back({a,b});
    }
    sort(v.begin(), v.end(), cmp);
    v.push_back(v[0]);
    vector <Radu> q;
    q.push_back(v[0]);
    for( int i = 1; i < v.size(); i++ ){
        Radu punct = v[i];
        if( q.size() == 1 )
            q.push_back(punct);
        else{
            int len = q.size();
            while( q.size() > 1 && !convex(q[len-2], q[len-1], punct) ){
//                cout << q[len-2].x << " " << q[len-2].y << " " << q[len-1].x << " " << q[len-1].y << " " <<  punct.x << " " << punct.y << "\n";
                q.pop_back();
                len--;
            }
            q.push_back(punct);
        }
    }
    q.pop_back();
    out << q.size() << "\n";
    for( auto i : q )
        out << fixed << setprecision(6) << i.x << " " << i.y << "\n";

    return 0;
}